List k-critical graphs without long induced paths

Home

CAAGT


Authors

Maria Chudnovsky

Jan Goedgebeur

Oliver Schaudt

Mingxian Zhong

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.

Installation instructions:
  • 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.

Installation instructions:
  • 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.

Last update: October 29, 2019.