k-Colorable Graph

A graph having chromatic number is called a -colorable graph (Harary 1994, p. 127). In contrast, a graph having is said to be a k-chromatic graph. Note that -colorable graphs are related but distinct from -colored graphs.

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

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

The 1, 2, 4, and 11, and 33 distinct simple 4-colorable graphs on , ..., 5 nodes are illustrated above.

The following table gives the numbers of -colorable simple graphs on 1, 2, ... nodes for small .

	OEIS	simple graphs on , 2, ... nodes having
2	A033995	1, 2, 3, 7, 13, 35, 88, 303, 1119, ...
3	A076315	1, 2, 4, 10, 29, 119, 667, 6024, 88500, ...
4	A076316	1, 2, 4, 11, 33, 150, 985, 11390, 243791, ...
5	A076317	1, 2, 4, 11, 34, 155, 1037, 12257, 272513, ...
6	A076318	1, 2, 4, 11, 34, 156, 1043, 12338, 274541, ...
7	A076319	1, 2, 4, 11, 34, 156, 1044, 12345, 274659, ...
8	A076320	1, 2, 4, 11, 34, 156, 1044, 12346, 274667, ...
9	A076321	1, 2, 4, 11, 34, 156, 1044, 12346, 274668, ...

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

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

The 1, 1, 2, and 6, and 20 distinct simple connected 4-colorable graphs on , ..., 5 nodes are illustrated above.

The following table gives the numbers of -colorable simple connected graphs on 1, 2, ... nodes for small .

	OEIS	simple connected graphs on , 2, ... nodes having
2	A005142	1, 1, 1, 3, 5, 17, 44, 182, 730, ...
3	A076322	1, 1, 2, 5, 17, 81, 519, 5218, 81677, ...
4	A076323	1, 1, 2, 6, 20, 107, 801, 10227, 231228, ...
5	A076324	1, 1, 2, 6, 21, 111, 847, 11036, 259022, ...
6	A076325	1, 1, 2, 6, 21, 112, 852, 11110, 260962, ...
7	A076326	1, 1, 2, 6, 21, 112, 853, 11116, 261072, ...
8	A076327	1, 1, 2, 6, 21, 112, 853, 11117, 261079, ...
9	A076328	1, 1, 2, 6, 21, 112, 853, 11117, 261080, ...

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

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

The following table gives the numbers of labeled -colorable graphs on 1, 2, ... nodes for small . The sequence (OEIS A047864) of 2-colorable labeled graphs on nodes has a rather remarkable generating function, as discussed by Wilf (1994, p. 89). Define

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

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

	OEIS	labeled graphs on , 2, ... nodes having
1		1, 1, 1, 1, 1, 1, ...
2	A047864	1, 2, 7, 41, 376, 5177, ...
3	A084279	1, 2, 8, 63, 958, 27554, ...
4	A084280	1, 2, 8, 64, 1023, 32596, ...
5	A084281	1, 2, 8, 64, 1024, 32767, ...
6	A084282	1, 2, 8, 64, 1024, 32768, ...

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

The 1, 4, and 37 distinct simple connected labeled 3-colorable graphs on , 3, and 4 nodes are illustrated above.

The following table gives the numbers of connected labeled -colorable graphs on 1, 2, ... nodes for small .

	OEIS	connected labeled graphs on , 2, ... nodes having
1		1, 0, 0, 0, 0, ...
2	A001832	1, 1, 3, 19, 195, 3031, 67263, ...
3	A084283	1, 1, 4, 37, 667, 21886, ...
4	A084284	1, 1, 4, 38, 727, 26538, ...
5	A084285	1, 1, 4, 38, 728, 26703, ...
6	A084286	1, 1, 4, 38, 728, 26704, ...

Wolfram Web Resources