k-Colorable Graph
A graph G having chromatic number chi(G)<=k is called a k-colorable graph (Harary 1994, p. 127). In contrast, a graph having chi(G)=k is said to be a k-chromatic graph. Note that k-colorable graphs are related but distinct from k-colored graphs.
The 1, 2, 3, and 7, and 13 distinct simple 2-colorable graphs on n=1, ..., 5 nodes are illustrated above.
The 1, 2, 4, and 10, and 29 distinct simple 3-colorable graphs on n=1, ..., 5 nodes are illustrated above.
The 1, 2, 4, and 11, and 33 distinct simple 4-colorable graphs on n=1, ..., 5 nodes are illustrated above.
The following table gives the numbers of k-colorable simple graphs on 1, 2, ... nodes for small k.
The 1, 1, 1, 3, and 5 distinct simple connected 2-colorable graphs on n=1, ..., 5 nodes are illustrated above.
The 1, 1, 2, and 5, and 17 distinct simple connected 3-colorable graphs on n=1, ..., 5 nodes are illustrated above.
The 1, 1, 2, and 6, and 20 distinct simple connected 4-colorable graphs on n=1, ..., 5 nodes are illustrated above.
The following table gives the numbers of k-colorable simple connected graphs on 1, 2, ... nodes for small k.
The 2 and 7 distinct simple labeled 2-colorable graphs on n=2 and 3 nodes are illustrated above.
The 2 and 8 distinct simple labeled 3-colorable graphs on n=2 and 3 nodes are illustrated above.
The following table gives the numbers of labeled k-colorable graphs on 1, 2, ... nodes for small k. The sequence {beta_n}_(n=0)={1,1,2,7,41,376,5177,...} (OEIS A047864) of 2-colorable labeled graphs on n nodes has a rather remarkable generating function, as discussed by Wilf (1994, p. 89). Define
giving the sequence 1, 2, 6, 26, 162, ... (OEIS A047863). Then beta_n is given by
The corresponding problem of enumerating n-colorable graphs for n>2 appears to be very hard.
The 1, 3, and 19 distinct simple connected labeled 2-colorable graphs on n=2, 3, and 4 nodes are illustrated above.
The 1, 4, and 37 distinct simple connected labeled 3-colorable graphs on n=2, 3, and 4 nodes are illustrated above.
The following table gives the numbers of connected labeled k-colorable graphs on 1, 2, ... nodes for small k.
See also
Bicolorable Graph, Chromatic Number, Chromatic Polynomial, k-Coloring, k-Chromatic Graph, k-Colored Graph, Three-Colorable GraphExplore with Wolfram|Alpha
More things to try:
References
Finch, S. R. "Bipartite, k-Colorable and k-Colored Graphs." June 5, 2003. http://algo.inria.fr/bsolve/.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.Sloane, N. J. A. Sequences A001832/M3063, A005142/M2501, A033995, A047864, A076315, A076316, A076317, A076318, A076319, A076320, A076321, A076322, A076323, A076324, A076325, A076326, A076327, A076328, A084279, A084280, A084281, A084282, A084283, A084284, A084285, and A084286 in "The On-Line Encyclopedia of Integer Sequences."Thomassen, C. "The Number of k-Colorings of a Graph on a Fixed Surface." Disc. Math. 306, 3145-3153, 2006.Wilf, H. S. Generatingfunctionology, 2nd ed. New York: Academic Press, p. 89, 1993.Referenced on Wolfram|Alpha
k-Colorable GraphCite this as:
Weisstein, Eric W. "k-Colorable Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/k-ColorableGraph.html