TOPICS

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

Bipartite Graph, Chromatic Number, k-Chromatic Graph, k-Colorable Graph, Three-Colorable Graph

## Explore with Wolfram|Alpha

More things to try:

## 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."

## Referenced on Wolfram|Alpha

Bicolorable Graph

## Cite this as:

Weisstein, Eric W. "Bicolorable Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/BicolorableGraph.html