This page contains complete lists of critical H-free graphs. An H-free graph is a graph that does not containH 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. A graph G is k-vertex-critical H-free if G is H-free, k-chromatic, and every proper induced 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, 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), and the set of (k+1)-critical (P5,dart)-free graphs as NkP5Dart (where the dart is the graph obtained from a diamond by adding a new vertex and making it adjacent to exactly one vertex with degree 3 in the diamond). Moreover, N4P5Claw+P1 stands for the set of 5-critical (P5,Claw+P1)-free graphs,N4P5K1,4+P1 for the set of 5-critical (P5,K_{1,4}+P1)-free graphs (where K_{1,4} is the complete bipartite graph with partitions of size 1 and 4), and N4P5ComplK3+2P1 for the set of 5-critical (P5,Compl(K3+2P1))-free graphs (where Compl() denotes the complement of the given graphs).
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 |
N4P5Dart | 14 | 184 |
N5P5Dart | 58 | 18029 |
N6P5Dart | 331 | 6367701 |
N4P5Claw+P1 | 42 | 344 |
N4P5K1,4+P1 | 103 | 534 |
N4P5ComplK3+2P1 | 24 | 214 |
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-obstructionfor 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. They can 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 |
[1] M. Chudnovsky, J. Goedgebeur, O. Schaudt and M. Zhong, Obstructions for three-coloring graphs without induced paths on six vertices, Journal of Combinatorial Theory, Series B, 140:45-83, 2020.
[2] J. Goedgebeur and O. Schaudt, Exhaustive generation of k-critical H-free graphs, 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, SIAM Journal on Discrete Mathematics, 34(1):431-469, 2020.