List k-critical graphs without long induced paths
The algorithms used in the generators ListCriticalPfreeGraphs and ListSize2Obstructions are described in:
M. Chudnovsky, J. Goedgebeur, O. Schaudt and M. Zhong, Obstructions for three-coloring and list three-coloring H-free graphs, to appear in SIAM Journal on Discrete Mathematics, 40 pages, 2019. Preprint: (arXiv).
ListCriticalPfreeGraphs is a program for generating all list k-critical Pt-free graphs.
The generator can be downloaded here and a short manual can be found here. ListCriticalPfreeGraphs is released under the GNU General Public License (GPL) and has been tested on Linux and Mac OS X.
Download, extract and configure nauty (ListCriticalPfreeGraphs requires nauty 2.5 or a more recent version).
Compile nauty using the command: "make nautyW1.a"
Copy the following files to the ListCriticalPfreeGraphs directory:
naurng.h naututil.h nauty.h nautyW1.a splay.c
Compile ListCriticalPfreeGraphs using the command "make".
Execute the binary "list_critical_Pfree_graphs"
Note: a program for generating k-critical Pt-free graphs can be found here.
Several complete lists of list k-critical H-free graphs can be found at the House of Graphs.
ListSize2Obstructions is a program for generating obstructions for list k-colourability where each vertex has exactly two possible colours (also called k-propagation paths).
The generator can be downloaded here and a short manual can be found here. ListSize2Obstructions is released under the GNU General Public License (GPL) and has been tested on Linux and Mac OS X.
Compile ListSize2Obstructions using "gcc -O3 -mpopcnt listsize2_obstructions.c -o listsize2_obstructions".
Execute the binary "listsize2_obstructions"
Don't hesitate to contact us at jan.goedgebeur[at]ugent.be if you have any further questions or suggestions.