k-critical graphs without long induced paths |
HomeAuthorsMingxian Zhong |
k-critical graphs without long induced pathsCriticalPfreeGraphs 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:
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:
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. |