TOPICS
Search

k-Chromatic Graph


A k-chromatic graph is a graph G having chromatic number gamma(G)=k (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

There are 1, 2, 6, and 12 distinct 2-chromatic simple graphs on n=2, ..., 5 nodes. Examples are illustrated above.

3-Chromatic

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

4-Chromatic

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

The following table gives the number of unlabeled 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 connected 2-chromatic simple graphs on n=2, 3, 4, and 5 nodes are illustrated above.

3-ChromaticConnected

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

4-ChromaticConnected

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

The following table gives the number of unlabeled connected simple 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, ...
3A1267370, 0, 1, 2, 12, 64, 475, 5036, 80947, ...
4A1267380, 0, 0, 1, 3, 26, 282, 5009, 149551, ...
5A1267390, 0, 0, 0, 1, 4, 46, 809, 27794, ...
6A1267400, 0, 0, 0, 0, 1, 5, 74, 1940, ...
7A2417020, 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 2-chromatic simple graphs on n=2, 3, and 4 nodes are illustrated above.

3-ChromaticLabeled

The 1 and 22 labeled 3-chromatic simple 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 connected 2-chromatic simple graphs on n=2, 3, and 4 nodes are illustrated above.

3-ChromaticLabeledConnected

The 1 and 18 labeled connected 3-chromatic simple graphs on n=3 and 4 nodes are illustrated above.

The following table gives the number of labeled connected simple 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

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, A084268, A084269, A084270, A084271, A084272, A084273, A084274, A126737, A126738, A126739, A126740, and A241702 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.

Referenced on Wolfram|Alpha

k-Chromatic Graph

Cite this as:

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

Subject classifications