bipartite graph

A bipartite graph is a graph with a chromatic number of $2$ .

The following graph, for example, is bipartite:

\xymatrix{{\color[rgb]{1,0,0}A}\ar@{-}[rrr]\ar@{-}[rd]\ar@{-}[ddd]&&&{\color[% rgb]{0,0,1}B}\\ &{\color[rgb]{0,0,1}E}&{\color[rgb]{1,0,0}F}\ar@{-}[ur]\ar@{-}[l]\ar@{-}[d]&\\ &{\color[rgb]{1,0,0}H}\ar@{-}[u]\ar@{-}[r]\ar@{-}[dl]&{\color[rgb]{0,0,1}G}&\\ {\color[rgb]{0,0,1}D}&&&{\color[rgb]{1,0,0}C}\ar@{-}[uuu]\ar@{-}[lll]\ar@{-}[% ul]}

One way to think of a bipartite graph is by partitioning the vertices into two disjoint sets where vertices in one set are adjacent only to vertices in the other set. In the above graph, this may be more obvious with a different :

\xymatrix{{\color[rgb]{1,0,0}A}\ar@{-}[r]\ar@{-}[rd]\ar@{-}[rdd]&{\color[rgb]{% 0,0,1}E}\\ {\color[rgb]{1,0,0}F}\ar@{-}[ru]\ar@{-}[r]\ar@{-}[rdd]&{\color[rgb]{0,0,1}B}\\ {\color[rgb]{1,0,0}H}\ar@{-}[ruu]\ar@{-}[r]\ar@{-}[rd]&{\color[rgb]{0,0,1}D}\\ {\color[rgb]{1,0,0}C}\ar@{-}[ruu]\ar@{-}[ru]\ar@{-}[r]&{\color[rgb]{0,0,1}G}}

The two subsets are the two columns of vertices, all of which have the same colour.

A graph is bipartite if and only if all its cycles have even length. This is easy to see intuitively: any path of odd length on a bipartite must end on a vertex of the opposite colour from the beginning vertex and hence cannot be a cycle.

Title	bipartite graph
Canonical name	BipartiteGraph
Date of creation	2013-03-22 12:17:07
Last modified on	2013-03-22 12:17:07
Owner	mathcam (2727)
Last modified by	mathcam (2727)
Numerical id	9
Author	mathcam (2727)
Entry type	Definition
Classification	msc 05C15
Synonym	bipartite