A 
-colorable
graph is a graph 
having chromatic number 
(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 k-colored
graphs.
The 1, 2, 3, 7, and 13 distinct 2-colorable simple graphs on 
,
..., 5 nodes are illustrated above.
The 1, 2, 4, 10, and 29 distinct 3-colorable simple graphs on 
,
..., 5 nodes are illustrated above.
The 1, 2, 4, 11, and 33 distinct 4-colorable simple 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 connected 2-colorable simple graphs on 
, ..., 5 nodes are illustrated
above.
The 1, 1, 2, 5, and 17 distinct connected 3-colorable simple graphs on 
, ..., 5 nodes are illustrated
above.
The 1, 1, 2, 6, and 20 distinct connected 4-colorable simple graphs on 
, ..., 5 nodes are illustrated
above.
The following table gives the numbers of 
-colorable connected simple 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 labeled 2-colorable simple graphs on 
and 3 nodes are illustrated above.
The 2 and 8 distinct labeled 3-colorable simple 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 formal exponential
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 square root is taken as a formal power series with constant term 1. The corresponding problem of enumerating 
-colorable graphs
for 
appears to be very hard (Harary and Palmer 1973, p. 272).
 | 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 connected labeled 2-colorable simple graphs on 
, 3, and 4 nodes are illustrated
above.
The 1, 4, and 37 distinct connected labeled 3-colorable simple 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.