Source-linked AI summary
A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs
Petr A. Golovach, Matthew Johnson, Daniël Paulusma, Jian Song
TL;DR
The paper addresses the computational complexity of colouring and its variants on graph classes characterized by one or two forbidden induced subgraphs. It surveys known classifications and open cases across colouring, precolouring extension, list colouring, and choosability. The survey records both tractable and hard cases while identifying boundaries where complexity remains unresolved or depends on the graph-class restriction.
Problem
The survey addresses the need to collect and organize computational-complexity results for colouring problems on graph classes defined by one or two forbidden induced subgraphs.
Method
The paper surveys classifications, reductions, tractable results, hardness results, and open problems for colouring and its precolouring, list-colouring, and choosability variants.
Results
The survey reports polynomial-time, NP-complete, and unresolved cases across forbidden-subgraph classes, including linear-time LIST k-COLOURING for (K_r,s, P_t)-free graphs.
Takeaways & Limitations
The collected results show that colouring complexity can vary substantially with the forbidden-subgraph restriction and with the chosen colouring variant.
Takeaways & Limitations
The survey notes unresolved cases, including the complexity of LIST 4-COLOURING for (P2 + P3)-free graphs and questions distinguishing choosability across related forbidden-pattern classes.
Abstract
from arXiv · showhide
For a positive integer $k$, a $k$-colouring of a graph $G=(V,E)$ is a mapping $c: V\rightarrow\{1,2,...,k\}$ such that $c(u)\neq c(v)$ whenever $uv\in E$. The Colouring problem is to decide, for a given $G$ and $k$, whether a $k$-colouring of $G$ exists. If $k$ is fixed (that is, it is not part of the input), we have the decision problem $k$-Colouring instead. We survey known results on the computational complexity of Colouring and $k$-Colouring for graph classes that are characterized by one or two forbidden induced subgraphs. We also consider a number of variants: for example, where the problem is to extend a partial colouring, or where lists of permissible colours are given for each vertex.
1 Introduction
The survey introduces graph colouring and its variants, then examines their complexity on restricted graph classes, especially classes defined by forbidden induced subgraphs. It emphasizes relationships among variants and summarizes general-graph complexity and the broader motivation for studying restricted inputs.
- Definitions: Graph colouring labels vertices so adjacent vertices receive different colours, with the goal often being to decide whether a specified number of colours suffices.COLOURING includes k as part of the input, whereas k-COLOURING fixes k.
- Motivation and scope: The survey studies restricted inputs because general-graph colouring complexity is often known and because forbidden induced-subgraph classes have generated many results requiring systematic collection.Its stated scope is graph classes characterized by the absence of one or two forbidden induced subgraphs.
- Variants: Partial-colouring and list-colouring variants constrain extensions or assign each vertex a set of admissible colours.The survey defines PRECOLOURING EXTENSION, k-PRECOLOURING EXTENSION, LIST COLOURING, ℓ-LIST COLOURING, and LIST k-COLOURING.
- Relationships among variants: k-COLOURING is a special case of k-PRECOLOURING EXTENSION, which is a special case of LIST k-COLOURING; LIST k-COLOURING is also a special case of k-LIST COLOURING.The relationships remain valid when inputs are restricted to particular graph classes.
- Relationships among variants: When ℓ≥k, k-COLOURING is not a special case of ℓ-COLOURING, because the former takes only a graph as input and their restricted-class complexities can differ.For planar graphs, 3-COLOURING is NP-complete whereas 4-COLOURING is polynomial-time solvable.
- General-graph complexity: On general graphs, k-COLOURING, k-PRECOLOURING EXTENSION, LIST k-COLOURING, and k-LIST COLOURING are polynomial-time solvable for k≤2 and NP-complete for k≥3.These classifications follow from the general-graph results and the relationships among the variants.
2 Results and Open Problems for H-Free Graphs
The survey assembles complexity classifications for colouring, precolouring extension, list colouring, and choosability on H-free graphs. It identifies broad dichotomies while retaining several unresolved cases and limitations.
- Colouring and extensions: Colouring is polynomial-time solvable on H-free graphs when H is an induced subgraph of P4 or P1 + P3, and NP-complete otherwise.
- Hardness results: For all k ≥3, k-COLOURING is NP-complete on graphs of sufficiently large girth and bounded maximum degree, and on line graphs of k-regular graphs.
- Dichotomies: For forbidden graphs with at most six vertices, the complexity of 3-COLOURING, 3-PRECOLOURING EXTENSION, and LIST 3-COLOURING is polynomial-time solvable exactly for linear forests.
- Dichotomies: For H with at most five vertices, 4-COLOURING and 4-PRECOLOURING EXTENSION are polynomial-time solvable exactly when H is a linear forest.
- Dichotomies: For H with at most four vertices and k ≥5, k-COLOURING, k-PRECOLOURING EXTENSION, and LIST k-COLOURING are polynomial-time solvable exactly for linear forests.
- Open problems: The classification remains incomplete for LIST 4-COLOURING on (P2 + P3)-free graphs and for 4-COLOURING on P6-free graphs.
- Choosability: CHOOSABILITY is NP-hard for H-free graphs when H is outside the listed exceptional set, but is polynomial-time solvable for H in {P1, 2P1, 3P1, P2, P3}.
3 Results and Open Problems for (H1, H2)-Free Graphs
The survey establishes broad hardness and tractability classifications for Colouring on graphs defined by two forbidden induced subgraphs, while identifying substantial unresolved cases and variant-specific boundaries.
- Hardness results: 3-COLOURING is NP-complete for C3-free graphs with maximum degree at most 4.
- Colourability bounds: Every (Kr, Pt)-free graph can be coloured with at most (t −2)r−2 colours, and LIST k-COLOURING is solvable in linear time on (Kr,s, Pt)-free graphs.
- Structural algorithms: Bounded clique-width implies polynomial-time solvability of Colouring for graph classes satisfying the relevant structural condition.The survey applies this framework to several (H1, H2)-free classes, including classes involving P1 + P4 and P5.
- Classification results: Theorem 21 gives multiple structural conditions yielding NP-completeness or polynomial-time solvability for Colouring on (H1, H2)-free graphs.The hardness conditions include cycles, claws, and several specified graph families; the tractable conditions include restrictions involving paths, forests, and small graph combinations.
- Open problems: The classification remains incomplete for Colouring, PRECOLOURING EXTENSION, and related fixed-colour and list-colouring variants.Open problems include completing the classifications for (H1, H2)-free graphs and for PRECOLOURING EXTENSION; PRECOLOURING EXTENSION is already NP-complete for (C3, P6)-free graphs.
- List-colouring variants: LIST COLOURING is polynomial-time solvable in three stated cases, whereas in all other cases even 3-LIST COLOURING is NP-complete for (H1, H2)-free graphs.The tractable cases involve an induced subgraph of P3, the pair C3 and K1,3, or a clique together with an independent set.
4 Graph Classes Defined by Other Forbidden Patterns
The survey extends colouring-complexity results beyond induced-subgraph restrictions to strongly forbidden, minor-free, and topological-minor-free graph classes. It gives several dichotomies and tractability results, while identifying substantial unresolved classifications.
- Strongly forbidden subgraphs: For graphs with at most seven vertices, COLOURING on strongly H-free graphs is polynomial-time solvable when H is a forest of maximum degree at most four, and NP-complete otherwise.This theorem gives a complete size-bounded classification for the stated family of forbidden graphs.
- Strongly forbidden subgraphs: LIST COLOURING is polynomial-time solvable on strongly (H1, ..., Hp)-free graphs when one forbidden graph is a suitable subcubic forest, whereas LIST 3-COLOURING is NP-complete in all other cases.The tractable forest has components with at most one vertex of degree 3.
- Minor-free graphs: For a fixed H, LIST COLOURING is polynomial-time solvable on H-minor-free graphs when H is planar, while 3-COLOURING is NP-complete when H is non-planar.The tractable side follows from bounded treewidth and the stated treewidth algorithm for list colouring; the hard side follows from planar graph hardness.
- Topological-minor-free graphs: For all r ≥3, COLOURING is polynomial-time solvable on Cr-topological-minor-free graphs, but the broader classification for topological-minor-free classes remains open.The survey also notes that topological-minor-free, minor-free, and strongly forbidden classes can have different colouring complexity.
- Choosability: CHOOSABILITY is linear-time solvable on H-minor-free graphs when H is planar, whereas even 3-CHOOSABILITY is Πp2-hard when H is non-planar.For strongly H-free graphs, the analogous tractable condition is a subcubic forest with restricted degree-3 components, while non-planarity or an odd cycle yields hardness.
Appendix
The appendix makes several list-colouring results explicit, transferring known precolouring-extension arguments and proving reductions between colouring and choosability. It establishes polynomial-time solvability results for specific graph classes and an NP-hardness transfer under closure by dominating vertices.
- Appendix scope: The appendix supplies proofs for three survey results that were not explicit in the literature, reflecting earlier emphasis on k-COLOURING and precolouring extension rather than list colouring.The proofs translate known precolouring-extension results and adjust existing arguments for choosability.
- List-colouring results: Theorem 40 transfers polynomial-time solvability of LIST 3-COLOURING from H-free graphs to (P1 + H)-free graphs.The proof guesses a list-respecting colouring of an induced copy of H and then applies the corresponding precolouring-extension argument.
- List-colouring results: Theorem 41 states that LIST 3-COLOURING is polynomial-time solvable on sP3-free graphs for every fixed integer s ≥1.The proof reuses the algorithm for 3-PRECOLOURING EXTENSION by treating vertices with lists of at most two colours as precoloured.
- Hardness transfer: If a graph class is closed under adding dominating vertices and COLOURING is NP-hard on it, then CHOOSABILITY is NP-hard on the same class.The reduction augments instances with dominating vertices while preserving the relevant colourability equivalence and class membership.
- Reduction proof: The colouring-to-choosability reduction adds a clique of k∗−k dominating vertices, where k∗=k+P, and proves G is k-colourable if and only if the augmented graph is k∗-choosable.The construction colours the added vertices first and deletes original vertices once enough unavailable list colours guarantee a later extension.
- Reduction proof: When every added vertex receives a colour absent from some remaining original-vertex list, the procedure deletes all original vertices and completes the choosability proof.The argument uses |T|=k∗−k=P and the threshold degG(u)−k+1 for deletion.