Short manual of CriticalPfreeGraphs
-----------------------------------
Author: Jan Goedgebeur (jan.goedgebeur@ugent.be)
In collaboration with: Maria Chudnovsky, Oliver Schaudt and Mingxian Zhong
Tripodgenerator is a generator for 4-critical Pt-free graphs.
This program has been tested on Linux and Mac OS X.
Installation
------------
The latest version of triangleramsey can be obtained from http://caagt.ugent.be/criticalpfree/
Compile the program using the command: cc -DWORDSIZE=32 -DMAXN=WORDSIZE -O4 critical_Pfree_graphs.c planarity.c nautyW1.a -o critical_Pfree_graphs
Usage
-----
An overview of all options can also be found by executing "./critical_Pfree_graphs -h".
Usage: ./critical_Pfree_graphs c P [options]
At least the number of vertices, c and P must be specified.
Valid options are:
c: Searches for -critical graphs (i.e. graphs which are NOT -colourable).
P: Searches for P-free graphs (i.e. graphs which do not contain P as induced subgraph).
C: Searches for C-free graphs (i.e. graphs which do not contain C as induced subgraph).
diamondfree: Only output diamond-free graphs.
dart: Only output dart-free graphs.
Gem: Only output gem-free graphs.
K13P1: Only output (K_{1,3}+P1)-free graphs.
K13P4: Only output (K_{1,4}+P1)-free graphs.
tripod: Only output tripod-free graphs (i.e. compl(K3+2P1)-free graphs).
g: Searches for graphs with girth at least .
vertexcritical: Output vertex-critical instead of critical graphs.
mod : Splits the generation in (more or less equally big) parts. Here part will be executed.
The generated graphs are written to stdout and are encoded in multicode format (see Appendix A).
Don't hesitate to contact me at jan.goedgebeur@ugent.be if you have any further questions or suggestions.
Changelog
---------
2015-04-27: First release.
2023-09-13: Added support to generate dart-free and gem-free graphs.
2024-03-04: Added support to generate (K_{1,3}+P1)-free, (K_{1,4}+P1)-free and tripod-free graphs.
Appendix A: definition of the multicode format
----------------------------------------------
This code is binary. The first entry is the number of vertices.
Vertices are numbered 1,...,n. For each vertex x there is a list of
neighbours with higher labels than x, followed by a zero.
The last list is always empty (there are no neighbours of n with a higher number than n),
therefore the last "list" is not followed by a zero.
After the last byte the next graph follows.
The codelength of a graph in multicode is number of vertices + number of edges.
More information about this format + a program to translate multicode to adjacency lists can be found at: http://hog.grinvin.org/Formats.action#multicode