A bicolorable graph
is a graph with chromatic number. A graph is bicolorable iff
it has no odd graph cycles (König 1950, p. 170;
Skiena 1990, p. 213; Harary 1994, p. 127). Bicolorable graphs are equivalent
to bipartite graphs (Skiena 1990, p. 213).
The numbers of bipartite graphs on , 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]].
is a graph with chromatic number 
. A graph is bicolorable iff
it has no odd graph cycles (König 1950, p. 170;
Skiena 1990, p. 213; Harary 1994, p. 127). Bicolorable graphs are equivalent
to bipartite graphs (Skiena 1990, p. 213).
The numbers of bipartite graphs on 
, 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]].
