Three-Colorable Graph

Author

Eric W. Weisstein
February 1, 2008

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Three-ColorableGraph.nb.

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

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

Enumeration

Timing[Length/@(chromatic3=Table[Select[Graphs[n],ChromaticNumber[#]==3&],{n,7}])]

Timing[Length/@(chromatic3=Table[Select[Graphs[n],ChromaticNumber[#]==3&],{n,8}])]

Timing[Length/@(chromatic3=Table[Select[Graphs[n],ChromaticNumber[#]==3&],{n,9}])]

ShowGraphArray[Flatten[Partition[#,8,8,{1,1},{}]&/@Map[RecognizeGraph,Take[chromatic3,5],{2}],
1],
VertexColor->Red,
VertexStyle->Disk[.15],
AspectRatio->Automatic,
GraphicsSpacing->.5]

Enumeration of Connected Three-Colorable

Length/@(chromatic3connected=Select[#,ConnectedQ]&/@chromatic3)

ShowGraphArray[Flatten[Partition[#,6,6,{1,1},{}]&/@Map[RecognizeGraph,Take[chromatic3connected,5],{2}],
1],
VertexColor->Red,
VertexStyle->Disk[.15],
AspectRatio->Automatic,
GraphicsSpacing->.5]