TOPICS
Search

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).

2-Chromatic

The 1, 2, 6, and 8 distinct simple 2-chromatic graphs on n=2, ..., 5 nodes are illustrated above.

3-Chromatic

The 1, 3, and 16 distinct simple 3-chromatic graphs on n=3, 4, and 5 nodes are illustrated above.

4-Chromatic

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.

gammaOEISsimple graphs on n=1, 2, ... nodes having chi(G)=gamma
1A0000121, 1, 1, 1, 1, 1, 1, ...
2A0762780, 1, 2, 6, 12, 34, 87, 302, 1118, ...
3A0762790, 0, 1, 3, 16, 84, 579, 5721, 87381, ...
4A0762800, 0, 0, 1, 4, 31, 318, 5366, 155291, ...
5A0762810, 0, 0, 0, 1, 5, 52, 867, 28722, ...
6A0762820, 0, 0, 0, 0, 1, 6, 81, 2028, ...
7A0762830, 0, 0, 0, 0, 0, 1, 7, 118, ...

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).

2-ChromaticConnected

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

3-ChromaticConnected

The 1, 2, and 12 simple connected 3-chromatic graphs on n=3, 4, and 5 nodes are illustrated above.

4-ChromaticConnected

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.

gammaOEISsimple connected graphs on n=1, 2, ...nodes having chi(G)=gamma
11, 0, 0, 0, 0, 0, ...
2A0051420, 1, 1, 3, 5, 17, 44, 182, 730, ...
3A0762840, 0, 1, 2, 12, 64, 475, 5036, 80947, ...
4A0762850, 0, 0, 1, 3, 26, 282, 5009, 149551, ...
5A0762860, 0, 0, 0, 1, 4, 46, 809, 27794, ...
6A0762870, 0, 0, 0, 0, 1, 5, 74, 1940, ...
7A0762880, 0, 0, 0, 0, 0, 1, 6, 110, ...

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).

2-ChromaticLabeled

The 1, 6, and 40 labeled simple 2-chromatic graphs on n=2, 3, 4, and 5 nodes are illustrated above.

3-ChromaticLabeled

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.

gammaOEISlabeled simple graphs on n=1, 2, ... nodes having chi(G)=gamma
11, 1, 1, 1, 1, 1, ...
2A0842700, 1, 6, 40, 375, 5176, ...
3A0842710, 0, 1, 22, 582, 22377, ...
4A0842720, 0, 0, 1, 65, 5042, ...
50, 0, 0, 0, 1, 171, ...
2-ChromaticLabeledConnected

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

3-ChromaticLabeledConnected

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.

gammaOEISlabeled simple connected graphs on n=1, 2, ... nodes having chi(G)=gamma
11, 0, 0, 0, 0, 0, ...
2A0018320, 1, 3, 19, 195, 3031, ...
3A0842730, 0, 1, 18, 472, 18855, ...
4A0842740, 0, 0, 1, 60, 4652, ...
50, 0, 0, 0, 1, 165, ...

See also

Chromatic Number, Chromatic Polynomial, k-Colorable Graph, k-Colored Graph

Explore with Wolfram|Alpha

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 Graph

Cite this as:

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

Subject classifications