Source-linked AI summary
Obstructions to $k$-colouring $H$-free graphs
Iain Beaton, Ben Cameron, Adam van Omme
TL;DR
The paper asks which forbidden induced subgraphs H yield only finitely many critical obstructions to k-colouring, a question connected to certifying algorithms. It proves the characterization for k ≥ 5 using co-tree structure and establishes the corresponding finiteness criterion.
Problem
The paper addresses which H-free hereditary classes have only finitely many critical obstructions to k-colouring, relevant because finite obstruction sets can provide efficiently verifiable “no” certificates.
Source: §1 · pp. 1–2Method
Results
For fixed k ≥ 5, there are finitely many k-vertex-critical H-free graphs if and only if H is an induced subgraph of P4 + ℓP1 for some ℓ ≥ 0.
Source: §1 · p. 3Takeaways & Limitations
The finiteness result implies polynomial-time certifying k-Colouring algorithms for (P4 + ℓP1)-free graphs for all k ≥ 1 and ℓ ≥ 0.
Source: §1 · p. 3
Abstract
from arXiv · showhide
A graph is $H$-free if it has no induced subgraph isomorphic to $H$. In 2020, Chudnovsky, Goedgebeur, Schaudt, and Zhong characterized all graphs $H$ such that there are only finitely many minimal obstructions to $3$-colouring $H$-free graphs. In general, the minimal obstructions to $k$-colouring $H$-free graphs are the $(k+1)$-vertex-critical $H$-free graphs, those are, the $H$-free graphs $G$ with $\chi(G)=k+1$ but $\chi(G-v)=k$ for every vertex in $G$. In this paper we complete the characterization for all $k > 4$ by showing that there are onky finitely $k$-vertex-critical $H$-free graphs if and only if $H$ is an induced subgraph of $P_4+\ell P_1$ for some $\ell \geq 0$.
1 Introduction
The introduction frames finite critical-graph obstructions as a route to certifying k-Colouring on hereditary classes and completes the finiteness characterization for k ≥ 5. The result resolves the stated conjecture for every ℓ ≥ 0.
1 Introduction
- A finite set of minimal obstructions can support efficiently verifiable “no” certificates because k-colourability is hereditary.The paper identifies minimal obstructions with critical graphs and describes iterative induced-subgraph search.Source: §1 · p. 1
- The introduction defines H-free graphs by forbidding H as an induced subgraph and situates the theorem among results on hereditary subclasses of P5-free graphs.Prior work showed infinitely many critical graphs when H contains an induced 2P2, claw, or cycle for the stated ranges of k.Source: §1 · pp. 1–2
- There are finitely many 4-vertex-critical H-free graphs if and only if H is an induced subgraph of P6, 2P3, or P4 + ℓP1 for any ℓ ≥ 0.Source: §1 · p. 2
- The conjecture arose because prior results had settled several subclasses, while the case H = P4 + ℓP1 remained to be determined for k > 4 and ℓ > 0.In particular, ℓ = 1 and k = 5 remained open.Source: §1 · p. 3
- For fixed k ≥ 5, there are finitely many k-vertex-critical H-free graphs exactly when H is an induced subgraph of P4 + ℓP1 for some ℓ ≥ 0.This proves Conjecture 1.2 for all k and ℓ.Source: §1 · p. 3
- The theorem implies polynomial-time certifying k-Colouring algorithms for (P4 + ℓP1)-free graphs for all k ≥ 1 and ℓ ≥ 0.Finite obstruction sets allow “no” certificates by induced-subgraph search.Source: §1 · pp. 1, 3
2 Preliminaries
The preliminaries establish graph notation and structural tools for the proof. In particular, they introduce reduced co-trees for P4-free graphs and record lemmas used later.
2 Preliminaries
- The notation section defines open and closed neighbourhoods, non-neighbourhoods, completeness, anticompleteness, modules, and disjoint union.It also uses mG for the disjoint union of m copies of G.Source: §2 · p. 3
- A co-tree represents a co-graph through repeated collapses of maximal clique or independent-set modules, labelled 1 or 0, respectively.A reduced co-tree is the unique form in which every root-to-leaf path alternates between 0 and 1.Source: §2 · p. 3
- In a reduced co-tree of a P4-free graph, each tree vertex corresponds to a module, each non-leaf has at least two children, and labels alternate along root-to-leaf paths.These structural facts are stated in Observation 2.1.Source: §2 · pp. 3–4
- The preliminaries state a component criterion for mixed adjacency and a critical-graph lemma whose listed conditions include anticomplete X and Y with Y complete to N(X).They also introduce Ramsey-number notation and cite Ramsey’s theorem for its finiteness.Source: §2 · pp. 3–4
3 k-vertex-critical (P4 + ℓP1)-free graphs
The proof bounds the size of a k-vertex-critical (P4 + ℓP1)-free graph by bounding the non-neighbourhood of an independent set and applying Ramsey’s theorem.
3 k-vertex-critical (P4 + ℓP1)-free graphs
- The proof works within G[U], which is P4-free and therefore a co-graph represented by a reduced co-tree.The co-tree’s height and child counts are bounded to bound its order and thus the number of vertices in U.Source: §3 · p. 4
- The reduced co-tree has bounded height because a path with at least 2(k − 1) levels would yield a Kk in a proper subgraph of G.The path alternates join and disjoint-union nodes; selecting descendants at join nodes constructs the clique.Source: §3 · p. 4
- A large support belongs to a vertex complete or anticomplete to each component, while incomparable supports in one family intersect in at most ℓ − 1 indices.Supports index components to which a vertex is not complete; Claim 3.1 rules out mixed adjacency for large supports, and the intersection bound follows by forbidding an induced P4 + ℓP1.Source: §3 · pp. 4–5
- Strictly nested large supports in one family correspond to pairwise adjacent vertices, so each inclusion chain has at most k − 1 members.The chain vertices together with their shared neighbour in S form a clique; Mirsky’s theorem then partitions each family into at most k − 1 antichains.Source: §3 · p. 5
- A Ramsey selection of I with size (k − 1)ℓ + 2 ensures every support either contains I or intersects I in at most ℓ indices.The proof colours (ℓ + 1)-subsets according to the antichains containing them and selects a homogeneous set.Source: §3 · p. 6
- Every module W of G[U] whose induced graph is disconnected has fewer than (k − 1)R connected components.The proof obtains this bound using criticality: deleting one component yields a (k − 1)-colouring, which is used to contradict the existence of too many components.Source: §3 · pp. 6–7
- A bounded co-tree for G[U] bounds |U|, and hence the independence number; Ramsey’s theorem then bounds the order of G.Here U is the non-neighbourhood of an arbitrary independent set S of size ℓ.Source: §3 · pp. 4, 7
4 Conclusion
The conclusion records the characterization for k ≥ 5 and places it among open questions about finite families of vertex-critical graphs in hereditary classes.
4 Conclusion
- The paper completely determines which graphs H have only finitely many k-vertex-critical H-free graphs for all k ≥ 5, noting H-free classes are among the most restrictive ways to define hereditary graph classes.Source: §4 · p. 8
- The authors pose the broader question of which hereditary graph classes contain only finitely many k-vertex-critical graphs.They also ask which H yield finiteness for (2P3, H)-free graphs for all k ≥ 1.Source: §4 · p. 8
- The conclusion relates further open cases to P6-free, 2P3-free, and (Pt, K3)-free classes, including a question about the smallest t with finitely many 4-vertex-critical graphs.For P6-free graphs, a finiteness result for a subclass could lead to polynomial-time k-Colouring algorithms, while k-Colouring remains NP-complete for P6-free graphs when k > 4.Source: §4 · p. 8
- The conclusion notes that infinitely many 5-vertex-critical (P5, K5)-free graphs coexist with no k-vertex-critical examples there for k ≥ 16.The text explains this behaviour by noting χ(K5) = 5 and that all such graphs are 15-colourable.Source: §4 · p. 8
- Open Problem 4.3 asks whether, for fixed k ≥ 4, a finite list with χ(Hi) < k yields, for some m ≥ k, infinitely many m-vertex-critical and (m + 1)-chromatic graphs but finitely many (m + 1)-vertex-critical graphs.The answer is no if every Hi has no universal vertex: joining a vertex to each graph in an infinite class of m-vertex-critical (H1, H2, . . . , Hn)-free graphs produces infinitely many (m + 1)-vertex-critical graphs in that class.Source: §4 · pp. 8–9
Declaration of AI-Assisted Content
The declaration describes model involvement in developing the proof and distinguishes that work from the authors’ later rewriting and review.
Declaration of AI-Assisted Content
- The model was prompted to construct infinite classes and investigate finiteness questions, and later supplied a proof of Theorem 1.3 that the first and second authors rewrote.The declaration says the proof’s key ideas included bounding the co-tree order in a non-neighbourhood and bounding the number of children of 0-nodes.Source: Declaration of AI-Assisted Content · p. 9
- The authors state that the introduction, conclusion, and declaration were written by the first and second authors, with the model used only for final proofreading.They take responsibility for the paper’s contents and correctness.Source: Declaration of AI-Assisted Content · p. 9