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 {beta_n}_(n=0)={1,1,2,7,41,376,5177,...}" src="https://mathworld.wolfram.com/images/equations/k-ColorableGraph/Inline27.svg" style="height:24px; width:312px" /> (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, ...

---

REFERENCES

Finch, S. R. "Bipartite, -Colorable and -Colored Graphs." June 5, 2003.

 http://algo.inria.fr/bsolve/.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.

Sloane, N. J. A. Sequences A001832/M3063, A005142/M2501, A033995, A047864, A076315, A076316, A076317, A076318, A076319, A076320, A076321, A076322, A076323, A076324, A076325, A076326, A076327, A076328, A084279, A084280, A084281, A084282, A084283, A084284, A084285, and A084286 in "The On-Line Encyclopedia of Integer Sequences.

"Wilf, H. S. Generatingfunctionology, 2nd ed. New York: Academic Press, p. 89, 1993.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength