k-Chromatic Graph

A graph  having chromatic number  is called a -chromatic graph (Harary 1994, p. 127). In contrast, a graph having  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 , ..., 5 nodes are illustrated above.

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

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

The following table gives the number of simple graphs on , 2, ... nodes having specified chromatic number .

	OEIS	simple graphs on , 2, ... nodes having
1	A000012	1, 1, 1, 1, 1, 1, 1, ...
2	A076278	0, 1, 2, 6, 12, 34, 87, 302, 1118, ...
3	A076279	0, 0, 1, 3, 16, 84, 579, 5721, 87381, ...
4	A076280	0, 0, 0, 1, 4, 31, 318, 5366, 155291, ...
5	A076281	0, 0, 0, 0, 1, 5, 52, 867, 28722, ...
6	A076282	0, 0, 0, 0, 0, 1, 6, 81, 2028, ...
7	A076283	0, 0, 0, 0, 0, 0, 1, 7, 118, ...

The triangle of numbers of graphs on  nodes having chromatic numbers 1, ...,  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 , 3, 4, and 5 nodes are illustrated above.

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

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

The following table gives the number of simple connected graphs on , 2, ... nodes having specified chromatic number .

	OEIS	simple connected graphs on , 2, ...nodes having
1		1, 0, 0, 0, 0, 0, ...
2	A005142	0, 1, 1, 3, 5, 17, 44, 182, 730, ...
3	A076284	0, 0, 1, 2, 12, 64, 475, 5036, 80947, ...
4	A076285	0, 0, 0, 1, 3, 26, 282, 5009, 149551, ...
5	A076286	0, 0, 0, 0, 1, 4, 46, 809, 27794, ...
6	A076287	0, 0, 0, 0, 0, 1, 5, 74, 1940, ...
7	A076288	0, 0, 0, 0, 0, 0, 1, 6, 110, ...

The triangle of numbers of connected simple graphs on  nodes having chromatic numbers 1, ...,  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 , 3, 4, and 5 nodes are illustrated above.

The 1 and 22 labeled simple 3-chromatic graphs on  and 4 nodes are illustrated above.

The following table gives the number of labeled simple graphs on , 2, ... nodes having specified chromatic number .

	OEIS	labeled simple graphs on , 2, ... nodes having
1		1, 1, 1, 1, 1, 1, ...
2	A084270	0, 1, 6, 40, 375, 5176, ...
3	A084271	0, 0, 1, 22, 582, 22377, ...
4	A084272	0, 0, 0, 1, 65, 5042, ...
5		0, 0, 0, 0, 1, 171, ...

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

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

The following table gives the number of labeled simple connected graphs on , 2, ... nodes having specified chromatic number .

	OEIS	labeled simple connected graphs on , 2, ... nodes having
1		1, 0, 0, 0, 0, 0, ...
2	A001832	0, 1, 3, 19, 195, 3031, ...
3	A084273	0, 0, 1, 18, 472, 18855, ...
4	A084274	0, 0, 0, 1, 60, 4652, ...
5		0, 0, 0, 0, 1, 165, ...

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, A076284, A076285, A076286, A076287, A076288, A084268, A084269, A084270, A084271, A084272,  A084273, and A084274 in "The On-Line Encyclopedia of Integer Sequences."