Bicolorable Graph

Author

Eric W. Weisstein
January 4, 2011

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

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

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

Examples

Grid[SortBy[GraphData[#,{"Name","V"}]&/@Select[Cases[GraphData["Bicolorable"],_String],!StringMatchQ[#,"Foster*"]&],Last],Dividers->True,Alignment->{{Left,Decimal},Automatic}]//TraditionalForm

Enumeration

All

V5

chromatic=Table[ChromaticNumber/@Graphs[n],{n,6}];//Timing

Length/@(bicolorable=Flatten/@Function[f,Position[f,_?(#≤2&)]]/@chromatic)

Length/@Table[GraphData["Bicolorable",n],{n,7}]

ShowGraphArray[Flatten[Partition[#,7,7,{1,1},{}]&/@(Table[MinimalColoring[#,Colors->{Red,Blue}]&/@RecognizeGraph/@Graphs[n][[bicolorable[[n]]]],{n,5}]),
1],
VertexStyle->Disk[.12],
GraphicsSpacing->.2
]

V8

GraphicsGrid[Map[ShowGraph[MinimalColoring[Graph[#],VertexColors->{Red,Blue}],PlotLabel->GraphData[#,"Name"]]&,Flatten[Partition[#,5,5,{1,1},{}]&/@Table[GraphData["Bicolorable",n],{n,5}],1],{2}],Dividers->All,ImageSize->500]

GraphicsGrid[Map[ShowGraph[MinimalColoring[Graph[#],VertexColors->{Red,Blue}],PlotLabel->GraphData[#,"Name"]]&,Flatten[Partition[#,5,5,{1,1},{}]&/@Table[GraphData["Bicolorable",n],{n,5}],1],{2}],Dividers->All,ImageSize->500]

Connected Graphs

Timing[Length/@(bicolorableconnected=Table[Select[Graphs[n][[bicolorable[[n]]]],ConnectedQ],{n,6}])]

ShowGraphArray[Flatten[Partition[#,7,7,{1,1},{}]&/@(Table[MinimalColoring[#,Colors->{Red,Blue}]&/@RecognizeGraph/@bicolorableconnected[[n]],{n,5}]),
1],
VertexStyle->Disk[.12],
GraphicsSpacing->.2
]