# Graph, bipartite

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

2020 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)