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, submitted, 2017. Preprint: arXiv:1707.07581