# nLab vertex coloring

A (proper) vertex coloring of a graph is a labelling of its vertices with the property that no two vertices sharing an edge have the same label, while an $n$-coloring is a vertex coloring using at most $n$ distinct labels. The chromatic number $\chi(G)$ of a graph $G$ is the least $n$ such that $G$ has an $n$-coloring.

Vertex coloring may also be expressed in terms of graph homomorphisms: a $n$-coloring of $G$ is the same thing as a graph homomorphism $G \to K_n$ into the complete graph on $n$ vertices. This formulation makes clear the duality between colorings and cliques: an $n$-clique in $G$ is the same thing as a homomorphism $K_n \to G$.

## References

• Chris Godsil and Gordon Royle (2001), Algebraic Graph Theory, Springer.

• Pavol Hell and Jaroslav Nešetřil (2001), Graphs and Homomorphisms, Oxford University Press.

Two posts by Tom Leinster at the n-Category Café on vertex-coloring and a categorical formulation of Hedetniemi’s conjecture:

Other references:

Last revised on September 8, 2018 at 18:49:26. See the history of this page for a list of all contributions to it.