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 .