Maximal triangle-free graphs and Ramsey graphs




Gunnar Brinkmann

Jan Goedgebeur

Jan-Christoph Schlage-Puchta

Maximal triangle-free graphs and Ramsey graphs

Triangleramsey is a program for the efficient generation of maximal triangle-free graphs. This generator can also be used to generate triangle Ramsey graphs for a given testgraph efficiently.

The algorithms used in the generator are described in:

  • 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.

The generator can be downloaded here and a short manual can be found here. Triangleramsey is released under the GNU General Public License (GPL) and has been tested on Linux and Mac OS X.

Installation instructions:

  • Download, extract and configure nauty (triangleramsey requires nauty 2.5 or a more recent version).
  • Copy the following files to the triangleramsey directory: naugraph.c nautil.c nauty.c nauty.h naurng.c naurng.h schreier.c schreier.h sorttemplates.c
  • Compile using the command "make".

The number of maximal triangle-free graphs can be found at the House of Graphs and various Ramsey graphs can be downloaded here.

Don't hesitate to contact us at jan.goedgebeur[at] if you have any further questions or suggestions.

Last update: June 28, 2012.