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

Related concepts

• knot coloring

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:

• Tom Leinster, “Colouring a Graph”, n-Category Café post of April 12, 2013.

• Tom Leinster, “Graph Colouring and Cartesian Closed Categories”, n-Category Café post of December 5, 2014.

Other references:

• Wikipedia: Graph coloring