Maximal triangle-free graphs

Home CAAGT Authors Stefan Brandt Gunnar Brinkmann Thomas Harmuth

Maximal triangle-free graphs MTF is a generator for maximal triangle-free graphs. This generator can also be used to generate Ramsey graphs for the generalized triangle Ramsey numbers R(K3, G). The algorithms used in the generator are described in: S. Brandt, G. Brinkmann, and T. Harmuth, The Generation of Maximal Triangle-Free Graphs, Graphs and Combinatorics, 16(2):149-157, 2000. 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. The generator can be downloaded here and a short manual can be found here. MTF has been tested on Linux and Mac OS X. Installation instructions: Download, extract and configure nauty (MTF requires nauty 2.4 or a more recent version). Copy the following files to the MTF directory: naugraph.c, nautil.c, nauty.c and nauty.h Compile MTF using "cc -DMAXN=1024 -DWORDSIZE=32 -O4 nauty.c nautil.c naugraph.c mtf.c -o mtf". The number of maximal triangle-free graphs can be found here. Note: A significantly faster generator for MTF graphs called Triangleramsey is available here.