TOPICS
Search

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.

2-Colorable

The 1, 2, 3, and 7, and 13 distinct simple 2-colorable graphs on n=1, ..., 5 nodes are illustrated above.

3-Colorable

The 1, 2, 4, and 10, and 29 distinct simple 3-colorable graphs on n=1, ..., 5 nodes are illustrated above.

4-Colorable

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.

gammaOEISsimple graphs on n=1, 2, ... nodes having chi(G)<=gamma
2A0339951, 2, 3, 7, 13, 35, 88, 303, 1119, ...
3A0763151, 2, 4, 10, 29, 119, 667, 6024, 88500, ...
4A0763161, 2, 4, 11, 33, 150, 985, 11390, 243791, ...
5A0763171, 2, 4, 11, 34, 155, 1037, 12257, 272513, ...
6A0763181, 2, 4, 11, 34, 156, 1043, 12338, 274541, ...
7A0763191, 2, 4, 11, 34, 156, 1044, 12345, 274659, ...
8A0763201, 2, 4, 11, 34, 156, 1044, 12346, 274667, ...
9A0763211, 2, 4, 11, 34, 156, 1044, 12346, 274668, ...
2-ColorableConnected

The 1, 1, 1, 3, and 5 distinct simple connected 2-colorable graphs on n=1, ..., 5 nodes are illustrated above.

3-ColorableConnected

The 1, 1, 2, and 5, and 17 distinct simple connected 3-colorable graphs on n=1, ..., 5 nodes are illustrated above.

4-ColorableConnected

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.

gammaOEISsimple connected graphs on n=1, 2, ... nodes having chi(G)<=gamma
2A0051421, 1, 1, 3, 5, 17, 44, 182, 730, ...
3A0763221, 1, 2, 5, 17, 81, 519, 5218, 81677, ...
4A0763231, 1, 2, 6, 20, 107, 801, 10227, 231228, ...
5A0763241, 1, 2, 6, 21, 111, 847, 11036, 259022, ...
6A0763251, 1, 2, 6, 21, 112, 852, 11110, 260962, ...
7A0763261, 1, 2, 6, 21, 112, 853, 11116, 261072, ...
8A0763271, 1, 2, 6, 21, 112, 853, 11117, 261079, ...
9A0763281, 1, 2, 6, 21, 112, 853, 11117, 261080, ...
2-ColorableLabeled

The 2 and 7 distinct simple labeled 2-colorable graphs on n=2 and 3 nodes are illustrated above.

3-ColorableLabeled

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

 gamma_n=sum_(k=0)^n2^(k(n-k))(n; k),

giving the sequence 1, 2, 6, 26, 162, ... (OEIS A047863). Then beta_n is given by

 sum_(n=0)^infty(beta_n)/(n!)x^n=sqrt(sum_(k=0)^infty(gamma_n)/(n!)x^n).

The corresponding problem of enumerating n-colorable graphs for n>2 appears to be very hard.

gammaOEISlabeled graphs on n=1, 2, ... nodes having chi(G)<=gamma
11, 1, 1, 1, 1, 1, ...
2A0478641, 2, 7, 41, 376, 5177, ...
3A0842791, 2, 8, 63, 958, 27554, ...
4A0842801, 2, 8, 64, 1023, 32596, ...
5A0842811, 2, 8, 64, 1024, 32767, ...
6A0842821, 2, 8, 64, 1024, 32768, ...
2-ColorableLabeledConnected

The 1, 3, and 19 distinct simple connected labeled 2-colorable graphs on n=2, 3, and 4 nodes are illustrated above.

3-ColorableLabeledConnected

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.

gammaOEISconnected labeled graphs on n=1, 2, ... nodes having chi(G)<=gamma
11, 0, 0, 0, 0, ...
2A0018321, 1, 3, 19, 195, 3031, 67263, ...
3A0842831, 1, 4, 37, 667, 21886, ...
4A0842841, 1, 4, 38, 727, 26538, ...
5A0842851, 1, 4, 38, 728, 26703, ...
6A0842861, 1, 4, 38, 728, 26704, ...

See also

Bicolorable Graph, Chromatic Number, Chromatic Polynomial, k-Coloring, k-Chromatic Graph, k-Colored Graph, Three-Colorable Graph

Explore with Wolfram|Alpha

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 Graph

Cite this as:

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

Subject classifications