Bipartite Graph (original) (raw)

Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology

Alphabetical Index New in MathWorld

BipartiteGraph

A bipartite graph, also called a bigraph, is a set of graph vertices decomposed into two disjoint sets such that no two graph vertices within the same set are adjacent. A bipartite graph is a special case of a _k_-partite graph with k=2. The illustration above shows some bipartite graphs, with vertices in each graph colored based on to which of the two disjoint sets they belong.

Bipartite graphs are equivalent to two-colorable graphs. All acyclic graphs are bipartite. A cyclic graph is bipartiteiff all its cycles are of even length (Skiena 1990, p. 213).

Families of bipartite graphs include

1. acyclic graphs (i.e., treesand forests),

2. book graphs S_(n+1) square P_2,

3. crossed prism graphs,

4. crown graphs K_2 square K_n^_,

5. cycle graphs C_(2k),

6. gear graphs,

7. grid graphs,

8. Haar graphs,

9. Hadamard graphs,

10. hypercube graphs Q_n,

11. knight graphs,

12. ladder graphs,

13. ladder rung graphs nP_2 (which are forests).

14. path graphs P_n (which are trees),

15. Mongolian tent graphs,

16. Sierpiński carpet graphs,

17. stacked book graphs,

18. star graphs S_n (which are trees).

König's line coloring theorem states that every bipartite graph is a class 1 graph. The König-Egeváry theorem states that the matching number (i.e., size of a maximum independent edge set) equals the vertex cover number (i.e., size of the smallest minimum vertex cover) are equal for a bipartite graph.

A graph may be tested in the Wolfram Language to see if it is a bipartite graph using BipartiteGraphQ[_g_], and the indices of one of the components of a bipartite graph can be found usingFindIndependentVertexSet[_g_][[1]].

BipartiteGraphs

The numbers of bipartite graphs on n=1, 2, ... nodes are 1, 2, 3, 7, 13, 35, 88, 303, ... (OEISA033995).

BipartiteConnectedGraphs

The numbers of connected bipartite graphs on n=1, 2 ... nodes are 1, 1, 1, 3, 5, 17, 44, 182, ... (OEIS A005142).

See also

Bicolorable Graph, Bicubic Graph, Bipartite Double Graph, Bipartite Kneser Graph, Complete Bipartite Graph,Graph Two-Coloring, _k_-Partite Graph, König-Egeváry Theorem,König's Line Coloring Theorem,Tutte Conjecture

Explore with Wolfram|Alpha

References

Chartrand, G. Introductory Graph Theory. New York: Dover, p. 116, 1985.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, 1998.Saaty, T. L. and Kainen, P. C. The Four-Color Problem: Assaults and Conquest. New York: Dover, p. 12, 1986.Skiena, S. "Coloring Bipartite Graphs." §5.5.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 213, 1990.Sloane, N. J. A. SequenceA033995 in "The On-Line Encyclopedia of Integer Sequences."Steinbach, P. Field Guide to Simple Graphs. Albuquerque, NM: Design Lab, 1990.

Referenced on Wolfram|Alpha

Bipartite Graph

Cite this as:

Weisstein, Eric W. "Bipartite Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/BipartiteGraph.html

Subject classifications