This page contains complete lists of critical H-free graphs.
An *H-free* graph is a graph that does not contain *H* as an induced subgraph.
A graph *G* is *k-chromatic* if it is k-colourable but not (k-1)-colourable.
We say that 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.

In [1] and [2] it is described how the following complete lists of critical H-free graphs were obtained.
The program *CriticalPfreeGraphs* which was used to generate these lists can be downloaded here.

The graph lists are currently only available in 'graph6' format.
We abbreviate the set of (k+1)-critical (Pt,Cu)-free graphs as *NkPtCu*
and the set of (k+1)-critical (Pt+Pu)-free graphs as *NkPt+Pu* (where Pt is a path with t vertices and Pt+Pu stands for the disjoint union of a Pt and a Pu).

Case | Critical graphs | Vertex-critical graphs |
---|---|---|

N3P6 | 24 | 80 |

planar N3P7 | 52 | 462 |

N3P7C4 | 17 | 35 |

N3P7C5 | 6 | 27 |

N3P8C4 | 94 | 164 |

N3P3+P2 | 17 | 50 |

N3P4+P1 | 4 | 9 |

Let *G* be a graph and let *L* be a mapping that maps each vertex of *G* to a subset of {1,...,k}.
We say that the pair *(G,L)* is *colourable* if there is a proper colouring *c* of *G* with *c(v) ∈ L(v)* for each *v ∈ V(G)*.
To this end, a pair *(G,L)* with *L(v) ⊆ {1,...,k}* is called a *list-obstruction* for k-colourability if *(G,L)* is not colourable.
If, moreover, for all proper induced subgraphs *H* of *G* the pair *(H,L _{V(H)})* is colourable, we call

The table below contains the counts of all P_{6}-free minimal list-obstructions for 3-colourability up to 9 vertices.
The obstructions up to 8 vertices can also be downloaded as adjacency lists.
In [3] it was proven that there are only finitely many P_{6}-free minimal list-obstructions for 3-colourability, but the exact number of obstructions is not known.
The program *ListCriticalPfreeGraphs* which was used to generate these minimal list-obstructions can be downloaded here.

Vertices | No. of list-obstructions |
---|---|

1 | 1 |

2 | 1 |

3 | 4 |

4 | 43 |

5 | 117 |

6 | 1806 |

7 | 34721 |

8 | 196231 |

9 | 1208483 |

≥ 10 | ? |

[1] M. Chudnovsky, J. Goedgebeur, O. Schaudt, and M. Zhong, Obstructions for three-coloring graphs with one forbidden induced subgraph, Proc. Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA16), Arlington, Virginia, USA, pages 1774-1783, 2016. Preprint: arXiv:1504.06979

[2] J. Goedgebeur and O. Schaudt, Journal of Graph Theory, 87(2):188-207, 2018.

[3] M. Chudnovsky, J. Goedgebeur, O. Schaudt, and M. Zhong, Obstructions for three-coloring and list three-coloring H-free graphs, submitted, 2017. Preprint: arXiv:1703.05684