Maximal triangle-free graphs




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.

Last update: March 12, 2012.