Bicolorable Graph

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]].

The following table lists some named bicolorable graphs.

graph
singleton graph	1
square graph	4
claw graph	4
utility graph	6
cubical graph	8
Herschel graph	11
Franklin graph	12
Heawood graph	14
tesseract graph	16
Möbius-Kantor graph	16
Hoffman graph	16
Pappus graph	18
Folkman graph	20
Desargues graph	20
truncated octahedral graph	24
Walther graph	25
Levi graph	30
Dyck graph	32
great rhombicuboctahedral graph	48
gray graph	54
Balaban 10-cage	70
Foster graph	90
great rhombicosidodecahedral graph	120
Tutte 12-cage	126

REFERENCES

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.

König, D. Theorie der endlichen und unendlichen Graphen. New York: Chelsea, 1950.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.Sloane, N. J. A. Sequence A033995 in "The On-Line Encyclopedia of Integer Sequences."