k-critical graphs without long induced paths




Maria Chudnovsky

Jan Goedgebeur

Oliver Schaudt

Mingxian Zhong

k-critical graphs without long induced paths

CriticalPfreeGraphs is a program for generating all k-critical Pt-free graphs.

The algorithm used in the generator is described in:

  • M. Chudnovsky, J. Goedgebeur, O. Schaudt, and M. Zhong, Obstructions for three-coloring graphs without induced paths on six vertices. Preprint: (arXiv).
  • J. Goedgebeur and O. Schaudt, Exhaustive generation of k-critical H-free graphs. Preprint: (arXiv).

The generator can be downloaded here and a short manual can be found here. CriticalPfreeGraphs 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 (CriticalPfreeGraphs requires nauty 2.5 or a more recent version).
  • Compile nauty using the command: "make nautyW1.a"
  • Copy the following files to the CriticalPfreeGraphs directory:
    naurng.h nausparse.h naututil.h nauty.h nautyW1.a planarity.c planarity.h splay.c
  • Compile CriticalPfreeGraphs using the command "make".
  • Execute the binary "critical_Pfree_graphs"

Note: a program for generating list k-critical Pt-free graphs can be found here.

Several complete lists of k-critical H-free graphs can be found at the House of Graphs.

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

Last update: May 22, 2015.