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$.
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:
Last revised on September 8, 2018 at 22:49:26. See the history of this page for a list of all contributions to it.