Page "Graph homomorphism" Paragraph 12

A graph coloring is an assignment of one of k colors to a graph G so that the endpoints of each edge have different colors, for some number k. Any coloring corresponds to a homomorphism from G to a complete graph K < sub > k </ sub >: the vertices of K < sub > k </ sub > correspond to the colors of G, and f maps each vertex of G with color c to the vertex of K < sub > k </ sub > that corresponds to c. This is a valid homomorphism because the endpoints of each edge of G are mapped to distinct vertices of K < sub > k </ sub >, and every two distinct vertices of K < sub > k </ sub > are connected by an edge, so every edge in G is mapped to an adjacent pair of vertices in K < sub > k </ sub >.

Conversely if f is a homomorphism from G to K < sub > k </ sub >, then one can color G by using the same color for two vertices in G whenever they are both mapped to the same vertex in K < sub > k </ sub >.

Because K < sub > k </ sub > has no edges that connect a vertex to itself, it is not possible for two adjacent vertices in G to both be mapped to the same vertex in K < sub > k </ sub >, so this gives a valid coloring.

That is, G has a k-coloring if and only if it has a homomorphism to K < sub > k </ sub >.