Kempe Chain

Author

Eric W. Weisstein
March 7, 2022

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/KempeChain.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/KempeChain.html.

©2022 Wolfram Research, Inc. except for portions noted otherwise

Small graphs that tangle Kempe chains

kempe=SortBy[GraphData["KempeCounterexample"],GraphData[#,"V"]&]

TextGrid[{GraphData[#,"V"],#}&/@kempe,Dividers->All]

From Stan Wagon, March 8, 2022:

For a graph to be a Kempe counterexample one must have an ordering of the vertices. Since there are n! orderings, it seems difficult to check.

Planar

GraphicsGrid[Partition[Show[GraphData[#]//StyleGraphs,PlotLabel->TextCell[Style[GraphData[#,"Name"],Directive[Italic,Black,FontFamily->"Times"]],PageWidth->120,TextAlignment->Center]]&/@kempe,UpTo[3]],ImageSize->500,Alignment->Top,Dividers->All]

3DUD

GraphicsGrid[Partition[Show[Graphics3D[GraphData[#,"Polyhedron"],Boxed->False],PlotLabel->TextCell[Style[GraphData[#,"Name"],Directive[Italic,Black,FontFamily->"Times"]]],PageWidth->120,TextAlignment->Center]&/@{"FritschGraph","PoussinGraph","ErreraGraph","KittellGraph"},UpTo[4]],ImageSize->500,Alignment->Top,Dividers->All]