|
|
|
|
bipartite graph
|
(Definition)
|
|
|
A bipartite graph is a graph with a chromatic number of  .
The following graph, for example, is bipartite:
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 representation:
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.
|
"bipartite graph" is owned by mathcam. [ full author list (2) | owner history (1) ]
|
|
(view preamble)
Cross-references: opposite, odd, path, length, even, cycles, colour, columns, subsets, obvious, adjacent, disjoint, vertices, chromatic number, graph
There are 12 references to this entry.
This is version 6 of bipartite graph, born on 2002-02-03, modified 2004-04-30.
Object id is 1765, canonical name is BipartiteGraph.
Accessed 20539 times total.
Classification:
| AMS MSC: | 05C15 (Combinatorics :: Graph theory :: Coloring of graphs and hypergraphs) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
![$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ {\color{red}A} \ar@{-}[rrr] \ar@... ...blue}D} & & & {\color{red}C} \ar@{-}[uuu] \ar@{-}[lll] \ar@{-}[ul] } } \end{xy}$](http://images.planetmath.org:8080/cache/objects/1765/l2h/img2.png "$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ {\color{red}A} \ar@{-}[rrr] \ar@... ...blue}D} & & & {\color{red}C} \ar@{-}[uuu] \ar@{-}[lll] \ar@{-}[ul] } } \end{xy}$")
![$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ {\color{red}A} \ar@{-}[r] \ar@{-... ...\color{red}C} \ar@{-}[ruu] \ar@{-}[ru] \ar@{-}[r] & {\color{blue}G}} } \end{xy}$](http://images.planetmath.org:8080/cache/objects/1765/l2h/img3.png "$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ {\color{red}A} \ar@{-}[r] \ar@{-... ...\color{red}C} \ar@{-}[ruu] \ar@{-}[ru] \ar@{-}[r] & {\color{blue}G}} } \end{xy}$")