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 nn-coloring is a vertex coloring using at most nn distinct labels. The chromatic number χ(G)\chi(G) of a graph GG is the least nn such that GG has an nn-coloring.

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


  • 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.