k-critical graphs without long induced paths

Home CAAGT Authors 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. 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. 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.