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