Graph, bipartite

Jump to: navigation, search

2010 Mathematics Subject Classification: Primary: 05C [MSN][ZBL]

bichromatic graph

A graph whose set \$V\$ of vertices can be partitioned into two disjoint sets \$V'\$ and \$V''\$ (i.e. \$V=V'\cup V''\$, \$V'\cap V''=\emptyset\$) so that each edge connects some vertex of \$V'\$ with some vertex of \$V''\$. A graph is bipartite if and only if all its simple cycles have even length. Another frequently used definition of a bipartite graph is a graph in which two subsets \$V'\$ and \$V''\$ of vertices (parts) are given in advance. Bipartite graphs are convenient for the representation of binary relations between elements of two different types — e.g. the elements of a given set and a subset of it yield the relation of "membership of an element to a subset", for executors and types of jobs one has the relation "a given executor can carry out a given job", etc.

An important problem concerning bipartite graphs is the study of matchings, that is, families of pairwise non-adjacent edges. Such problems occur, for example, in the theory of scheduling (partitioning of the edges of a bipartite graph into a minimal number of disjoint matchings), in the problem of assignment (finding the maximum number of elements in a matching), etc. The cardinality of the maximum matching in a bipartite graph is

\$\$|V'|-\max_{A'\subseteq V'}(|A'|-|V''(A')|),\$\$

where \$V''(A')\$ is the number of vertices of \$V''\$ adjacent to at least one vertex of \$A'\$. A complete bipartite graph is a bipartite graph in which any two vertices belonging to different subsets are connected by an edge (e.g. the graph \$K_{3,3}\$, see Graph, planar, Figure 1).

A generalization of the concept of a bipartite graph is the concept of a multipartite or \$k\$-partite graph, i.e. a graph in which the vertices are partitioned into \$k\$ subsets so that each edge connects vertices belonging to different subsets.

References

 [1] O. Ore, "Theory of graphs" , Amer. Math. Soc. (1962)

Comments

The complete bipartite graph on vertex sets of size \$a,b\$ is denoted \$K_{a,b}\$. Similarly the complete multipartite graph on \$k\$ vertex sets of sizes \$a_1,\ldots,a_k\$ is denoted \$K_{a_1,\ldots,a_k}\$. The complement of a complete multipartite \$K_{a_1,\ldots,a_k}\$ is a disjoint union of complete graphs \$K_{a_1} \sqcup \cdots \sqcup K_{a_k}\$.

References

 [a1] F. Harary, "Graph theory" , Addison-Wesley (1969) pp. Chapt. 9 [a2] R.J. Wilson, "Introduction to graph theory" , Longman (1985) [b1] Biggs, Norman Algebraic graph theory 2nd ed. Cambridge University Press (1994) ISBN 0-521-45897-8 Zbl 0797.05032
How to Cite This Entry:
Graph, bipartite. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Graph,_bipartite&oldid=52570
This article was adapted from an original article by V.B. Alekseev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article