logo

Maximal triangle-free graphs

In order to determine properties of all triangle-free graphs, it often suffices to investigate maximal triangle-free graphs. These are triangle-free graphs for which the insertion of any further edges would create a triangle. For triangle-free graphs of order n ≥ 3 being maximal triangle-free is equivalent to having diameter 2.

Maximal triangle-free graphs can also be used to determine the triangle Ramsey numbers R(K3, G) (see [1,2]). Various triangle Ramsey graphs are also present in the searchable database and can be found by searching for the keyword 'ramsey'.

The graph lists are currently only available in 'graph6' format. The larger files are compressed with gzip.

All numbers were independently confirmed by MTF and triangleramsey . The counts for 24 vertices were computed with triangleramsey in [3].

VerticesNo. of graphs
31
42
53
64
76
810
916
1031
1161
12147
13392
141274
155036
1625617
17164796
181337848
1913734745
20178587364
212911304940
2258919069858
231474647067521
2445599075629687
Go to top
References

[1] S. Brandt, G. Brinkmann and T. Harmuth, All Ramsey numbers r(K3,G) for connected graphs of order 9, Electron. J. Combinatorics, 5, R7, 1998.

[2] G. Brinkmann, J. Goedgebeur and J.C. Schlage-Puchta, Ramsey numbers R(K3,G) for graphs of order 10, Electronic Journal of Combinatorics, 19(4), 2012.

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


Copyright © 2010-2024 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