k-critical graphs without long induced paths
CriticalPfreeGraphs is a program for generating all k-critical Pt-free graphs. A graph G is k-critical H-free if G is H-free, k-chromatic, and every H-free proper subgraph of G is (k-1)-colourable.
The algorithm used in the generator is described in:
M. Chudnovsky, J. Goedgebeur, O. Schaudt and M. Zhong, Obstructions for three-coloring graphs with one forbidden induced subgraph,
In Proc. Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA16), Arlington, Virginia, USA, pages 1774-1783, 2016 (DOI).
J. Goedgebeur and O. Schaudt, Exhaustive generation of k-critical H-free graphs,
Journal of Graph Theory, 87(2):188-207, 2018 (arXiv | DOI).
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.