k-Chromatic Graph
A graph G having chromatic number gamma(G)=k is called a k-chromatic graph (Harary 1994, p. 127). In contrast, a graph having gamma(G)<=k is said to be a k-colorable graph. A graph is one-colorable iff it is totally disconnected (i.e., is an empty graph).
The 1, 2, 6, and 8 distinct simple 2-chromatic graphs on n=2, ..., 5 nodes are illustrated above.
The 1, 3, and 16 distinct simple 3-chromatic graphs on n=3, 4, and 5 nodes are illustrated above.
The 1 and 4 distinct simple 4-chromatic graphs on n=4 and 5 nodes are illustrated above.
The following table gives the number of simple graphs on n=1, 2, ... nodes having specified chromatic number gamma.
The triangle of numbers of graphs on n nodes having chromatic numbers 1, ..., n is therefore given by 1; 1, 1; 1, 2, 1; 1, 6, 3, 1;, 1, 12, ... (OEIS A084268).
The 1, 1, 3, and 5 simple connected 2-chromatic graphs on n=2, 3, 4, and 5 nodes are illustrated above.
The 1, 2, and 12 simple connected 3-chromatic graphs on n=3, 4, and 5 nodes are illustrated above.
The 1 and 3 simple connected 4-chromatic graphs on n=4 and 5 nodes are illustrated above.
The following table gives the number of simple connected graphs on n=1, 2, ... nodes having specified chromatic number gamma.
The triangle of numbers of connected simple graphs on n nodes having chromatic numbers 1, ..., n is therefore given by 1; 0, 1; 0, 1, 1; 0, 3, 2, 1; 0, 5, 12, ... (OEIS A084269).
The 1, 6, and 40 labeled simple 2-chromatic graphs on n=2, 3, 4, and 5 nodes are illustrated above.
The 1 and 22 labeled simple 3-chromatic graphs on n=3 and 4 nodes are illustrated above.
The following table gives the number of labeled simple graphs on n=1, 2, ... nodes having specified chromatic number gamma.
The 1, 3, and 19 labeled simple connected 2-chromatic graphs on n=2, 3, 4, and 5 nodes are illustrated above.
The 1 and 18 labeled simple connected 3-chromatic graphs on n=3 and 4 nodes are illustrated above.
The following table gives the number of labeled simple connected graphs on n=1, 2, ... nodes having specified chromatic number gamma.
See also
Chromatic Number, Chromatic Polynomial, k-Colorable Graph, k-Colored GraphExplore with Wolfram|Alpha
More things to try:
References
Thomassen, C. "The Number of k-Colorings of a Graph on a Fixed Surface." Disc. Math. 306, 3145-3153, 2006.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.Sloane, N. J. A. Sequences A000012/M0003, A001832/M3063, A005142/M2501, A076278, A076279, A076280, A076281, A076282, A076283, A076284, A076285, A076286, A076287, A076288, A084268, A084269, A084270, A084271, A084272, A084273, and A084274 in "The On-Line Encyclopedia of Integer Sequences."Referenced on Wolfram|Alpha
k-Chromatic GraphCite this as:
Weisstein, Eric W. "k-Chromatic Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/k-ChromaticGraph.html