A bicolorable graph G is a graph with chromatic number χ(G)<=2. A graph is bicolorable iff it has no odd graph cycles. Bicolorable graphs are equivalent to bipartite graphs. The numbers of bipartite graphs on n = 1, 2, ... nodes are 1, 2, 3, 7, 13, 35, 88, 303, ... (OEIS A033995). A graph can be tested for being bicolorable using BipartiteGraphQ[g], and one of its two bipartite sets of vertices can be found using FindIndependentVertexSet[g][[1]].

bipartite graph | chromatic number | k-chromatic graph | k-colorable graph | three-colorable graph