Bipartite Graph

Author

Eric W. Weisstein
June 14, 2023

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

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

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

Figure

BipartiteColoring[g_Graph]:=Annotate[g,{VertexStyle->Thread[VertexList[g]->FindVertexColoring[g,{Red,Black}]],VertexSize->{"Scaled",.05}}]

g1=BipartiteColoring[GraphData["CubicalGraph"]]

g2=BipartiteColoring[GraphData["UtilityGraph"]]

GraphicsRow[{g2,g1},ImageSize->400]

Counts

Simple

A033995

1, 2, 3, 7, 13, 35, 88, 303, 1119, 5479, 32303, 251135, 2527712, 33985853, 611846940,

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

Table[Count[Graphs[n,"Format"->"AdjacencyMatrix"],_?(BipartiteGraphQ[AdjacencyGraph[#]]&)],{n,9}]//Timing

Table[Count[Graphs[n,"Format"->"AdjacencyMatrix"],_?(BipartiteGraphQ[AdjacencyGraph[#]]&)],{n,10}]//Timing

Connected

A005142

1, 1, 1, 3, 5, 17, 44, 182, 730, 4032, 25598, 212780, 2241730, 31193324, 575252112,

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

Table[Count[ConnectedGraphs[n,"Format"->"AdjacencyMatrix"],_?(BipartiteGraphQ[AdjacencyGraph[#]]&)],{n,9}]//Timing

Table[Count[ConnectedGraphs[n,"Format"->"AdjacencyMatrix"],_?(BipartiteGraphQ[AdjacencyGraph[#]]&)],{n,10}]//Timing

Coloring

bug(304949)

(ivs=FindIndependentVertexSet[GraphData["Foster222A"]][[1]])//Timing

(twocol=TwoColoring[Graph["Foster222A"]])//Timing

Flatten[Position[twocol,1]]===ivs

data=Monitor[{GraphData[g=#,"V"],#,Timing[FindIndependentVertexSet[GraphData[#]][[1]]][[1]]/
Timing[i2=Flatten[Position[TwoColoring[Graph[#]],1]]][[1]]
}&/@GraphData[{"Cubic","Bipartite"},100;;200],g];

Grid[SortBy[data,First],Alignment->Left,Dividers->All]

Enumeration

All

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

Timing[Length/@(bipartite=Select[#,BipartiteQ]&/@Table[Graphs[n],{n,6}])]

Off[General::"stop"]

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

Connected

Timing[Length/@(bipartiteconnected=Select[#,ConnectedQ]&/@bipartite)]

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

Graphs with a bipartite connected component

http : // www.research.att.com/~njas/sequences/A157015

FindSequenceFunction[{1,2,3,8,18,60,232,1386,14174,291276,12307990,1031239601,166112993562,50667177892731,29104660317364802,31455540470952824360,64032442292149794564470,245999865227419124242896312,1787823661072649054471336315803}]

Table[Count[Graphs[n],_?(Function[g,Or@@BipartiteQ/@(InduceSubgraph[g,#]&/@ConnectedComponents[g])])],{n,7}]//Timing

Table[Count[Graphs[n],_?(Function[g,Or@@BipartiteQ/@(InduceSubgraph[g,#]&/@ConnectedComponents[g])])],{n,8}]//Timing

f[g_]:=Block[{c=ConnectedComponents[g]},If[
Length[c]===1,
BipartiteQ[g],
BipartiteQ[InduceSubgraph[g,#]]&/@Or@@ConnectedComponents[g]
]]

Table[Count[Graphs[n],_?f],{n,7}]//Timing

Table[Count[Graphs[n],_?f],{n,8}]//Timing

Table[Count[Graphs[n],_?(Function[g,If[
Length[c=ConnectedComponents[g]]===1,
BipartiteQ[g],
BipartiteQ[InduceSubgraph[g,#]]&/@Or@@ConnectedComponents[g]]
])],{n,8}]//Timing

Table[Count[Graphs[n],_?f],{n,7}]//Timing

Table[Count[Graphs[n],_?(Function[g,If[
Length[c=ConnectedComponents[g]]===1,
BipartiteQ[g],
BipartiteQ[InduceSubgraph[g,#]]&/@Or@@ConnectedComponents[g]]
])],{n,9}]//Timing

Families

GraphClassesThatAreClass["Bipartite"]

Table

Sort[{GraphData[#,"Name"],GraphData[#,"VertexCount"]}&/@GraphData["Bipartite"],Last[#1]<=Last[#2]&]//TableForm