vertex coloring (changes) in nLab

Showing changes from revision #3 to #4: Added | Removed | Changed

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. label, A while vertex an coloring which uses at mostnnnn-coloring labels is called a vertex coloring using at mostnn-coloringnn . A distinct labels. Thennchromatic number -coloring of a graphχ(G) G \chi(G) is of the same thing as a graph homomorphismG→K n G \to K_n into is the complete least graph onnn vertices, such and that is dual to the notion of n G n G - has ancliquenn -coloring. (which corresponds to a homomorphismK n→GK_n \to G).

Vertex coloring may also be expressed in terms of graph homomorphisms: a nn-coloring of GG is the same thing as a graph homomorphism G→K 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 n→GK_n \to G.

• 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

• Wikipedia: Graph coloring