This project contains a basic program for checking list-colorability of a graph.
This project requires nauty 2.6. Unzip the nauty source code into a directory called nauty adjacent to the root of this git repository. For example, I have one directory that contains a nauty folder and a Coloring folder.
Navigate to the src/ directory and type make. The binaries will be loaded into the bin/ directory.
To test a set of graphs, we use the lists program and pass the graph information through stdin using graph6 or sparse6 strings.
To test k-choosability, run lists --choosable -k [#colors], where #colors is the size of lists to use (k). The input is expected to be a list of grraph6 or sparse6 strings, separated by newlines.
To test f-choosability (choosability with lists of size f(v) on a vertex v), run lists --fchoosable. The input is expected to be a list of graph6 or sparse6 strings, followed (in a new line) by a list of integers representing f(v) for the vertices, in order.
To check reducibility with a given list of "external degrees" (or rather, computing f-choosability where f(v) = k - ext(v)), run lists --reducible -k [#colors] and the input is a list of graph6 or sparse6 strings, followed (in a new line) by a list of integers representing ext(v) for the vertices, in order.
Finally, all runs can be modified to restrict to choosability with separation by specifying -c [#] where the number given is the maximum number of common colors in adjacent lists.
For example, one could navigate to the bin directory after building and type the following command:"
lists --reducible -k 4 -c 2 --print < ../examples/reducible-k4c2.txt
This results in output that begins with the following for the first graph tested:
48 connected subgraphs
recursive calls: 619873
:Ea@_gMC is 4-reducible (with external degrees 0 2 1 2 1 2)
done in 0.31250 seconds.
These examples were used during the collaboration leading to (4,2)-choosability of planar graphs with forbidden structures.