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 |
In [1] it is proven that there are infinitely many 4-critical P7-free graphs. Nevertheless, in Table 2 of [1] all 4-critical and 4-vertex-critical P7-free graphs were determined for small orders. More specifically, there are exactly 2608 4-critical and exactly 62126 4-vertex-critical P7-free graphs with at most 16 vertices.
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,LV(H)) is colourable, we call (G,L) a minimal list-obstruction. (Here LV(H) denotes the restriction of L to the domain V(H)).
The table below contains the counts of all P6-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 P6-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, to appear in SIAM Journal on Discrete Mathematics, 40 pages, 2019.