A graph is k-chromatic if its chromatic number is equal to k. A k-vertex-critical graph is a k-chromatic graph for which every proper induced subgraph is (k-1)-colourable and a k-critical graph is a k-chromatic graph for which every proper subgraph is (k-1)-colourable. Finally, a maximal triangle-free graph (in short, an mtf graph, see also here) is a triangle-free graph such that the insertion of any new edge forms a triangle.
The graph lists are currently only available in 'graph6' format. The larger files are compressed with gzip. This page lists the counts of the smallest triangle-free 4- and 5-chromatic graphs. Please refer to [1] for more information on how these graphs were obtained.
| Vertices | All | Vertex-critical | Critial | Mtf |
|---|---|---|---|---|
| 11 | 1 | 1 | 1 | 1 |
| 12 | 24 | 4 | 2 | 5 |
| 13 | 1110 | 31 | 13 | 25 |
| 14 | 76261 | 1080 | 208 | 151 |
| 15 | 6461386 | 49015 | 5039 | 1019 |
| Vertices | All | Vertex-critical | Critial | Mtf |
|---|---|---|---|---|
| 22 | 80 | 80 | 21 | 15 |
| 23 | 315457 | 154899 | 4192 | 2729 |
| 24 | 1030077762 | 212827777 | 625812 | 369360 |
[1] J. Goedgebeur, On minimal triangle-free 6-chromatic graphs, Journal of Graph Theory, 93(1):34-48, 2020.