Mathematics — Graph Theory · coprimality-graph-colorings
Problem
Let n∈N. Let G be the n-th coprimality graph Copn defined in Example 2.1.3. Let k∈N. Let m be the number of prime numbers in the set {1,2,…,n}. Prove the following:
((a)) The graph G has a proper k-coloring if and only if k≥m+1.
((b)) The graph G has a subgraph isomorphic to Kk if and only if k≤m+1.