Bicolorable Graph


A bicolorable graph G is a graph with chromatic number chi(G)<=2. 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 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]].

See also

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

Explore with Wolfram|Alpha


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.

Subject classifications