Tait coloring

A Tait coloringMathworldPlanetmath of a trivalent (http://planetmath.org/ValencyPlanetmathPlanetmath) (aka cubic) graph is a coloringMathworldPlanetmath of its edges with only three colors, such that at each vertex the colors of the three edges there are different. After Peter G. Tait (1831–1901), Scottish physicist, who in 1880 proved the following

TheoremMathworldPlanetmath (Tait) A bridge-free trivalent plane graphMathworldPlanetmath can be face-colored with 4 colors if and only if it can be edge-colored with 3 colors.

This http://planetmath.org/node/6925introduction to face- and edge-colorings of plane graphs has a proof of the theorem.

To put this in a modern context, Vizing’s theorem says that graphs G fall into two classes: those that can be colored with Δ(G) colors and those that need Δ(G)+1 colors, where Δ(G) is the largest valency that occurs in G. When applied to trivalent graphs that means 3 and 4 colors, respectively. It is known that “almost all” are in the first class — this expression has a technical meaning (for increasing graph size, the proportion of them in the second class tends to zero).

Thanks to Tait’s result, it is a corollary of the four-color theorem that all planar trivalent graphs are in the first class (can be edge-3-colored). The converseMathworldPlanetmath is not the case. Many trivalent graphs, in fact almost all of them, can be edge-3-colored and yet are not planar. K3,3 is one example.

The Petersen graphMathworldPlanetmathPlanetmath is an example of a trivalent graph that needs 4 colors.

Title Tait coloring
Canonical name TaitColoring
Date of creation 2013-03-22 15:10:29
Last modified on 2013-03-22 15:10:29
Owner marijke (8873)
Last modified by marijke (8873)
Numerical id 9
Author marijke (8873)
Entry type Definition
Classification msc 05C15
Related topic ColoringsOfPlaneGraphs
Related topic VizingsTheorem