Triangle-free k-chromatic graphs

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.

Triangle-free 4-chromatic graphs

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

Triangle-free 5-chromatic graphs

Vertices All Vertex-critical Critial Mtf
22 80 80 21 15
23 315457 154899 4192 2729
24 1030077762 212827777 625812 369360

References

[1] J. Goedgebeur, On minimal triangle-free 6-chromatic graphs, submitted, 2017. Preprint: arXiv:1707.07581

Go to top