logo

Critical H-free graphs

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).

CaseCritical graphsVertex-critical graphs
N3P62480
planar N3P752462
N3P7C41735
N3P7C5627
N3P8C494164
N3P3+P21750
N3P4+P149
N4P5Dart14184
N5P5Dart5818029
N6P5Dart3316367701
N4P5Claw+P142344
N4P5K1,4+P1103534
N4P5ComplK3+2P124214
Go to top

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.

Obstructions for list 3-colouring

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 .

VerticesNo. of list-obstructions
11
21
34
443
5117
61806
734721
8196231
91208483
Go to top

[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.


Copyright © 2010-2024 Ghent University & KU Leuven

Our website uses functional cookies to enhance your user experience. By using this site, you agree to our use of cookies. Learn more

Close