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 
.
,
2, ... nodes having 
-Colorable and 
-Colored Graphs." June 5, 2003. 
-Colorings of a Graph on a Fixed Surface." Disc. Math. 306,
3145-3153, 2006.Wilf, H. S.