bigraph | two-colorable graph

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 bipartite iff all its cycles are of even length. Families of of bipartite graphs include 1. acyclic graphs (i.e., trees and forests), 2.

bicolorable graph | bicubic graph | bipartite double graph | bipartite Kneser graph | complete bipartite graph | graph two-coloring | König-Egeváry theorem | König's line coloring theorem | k-partite graph | Tutte conjecture