logo

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
VerticesAllVertex-criticalCriticalMtf
111111
1224425
131110311325
14762611080208151
1564613864901550391019
Go to top

Triangle-free 5-chromatic graphs
VerticesAllVertex-criticalCriticalMtf
2280802115
2331545715489941922729
241030077762212827777625812369360
Go to top

References

[1] J. Goedgebeur, On minimal triangle-free 6-chromatic graphs, Journal of Graph Theory, 93(1):34-48, 2020.


Copyright © 2010-2025 Ghent University & KU Leuven

Our website uses functional cookies to enhance your user experience. By using this site, you agree to our use of cookies. Learn more

Close