Skip to content
DraconiticResearch
Search Sources API
201,683 studies31 sourcesUpdated 55 min ago
PreprintCC BY-NC-SA 4.0arXiv

Obstructions to k-colouring H-free graphs

  • Iain Beaton
  • Ben Cameron
  • Adam van Omme
Open at sourcePDFDOICite

Abstract

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 χ(G)=k+1 but χ(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 P4+ℓ P1 for some ℓ ≥ 0.

Related

  1. Degreewise Cut-Semigroup Saturation for K5-Minor-Free Graphs and Seymour's Planar Edge-Colouring Conjecture
    SeungJu Lee
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Four colours are needed for closed-neighbourhood conflict-free colouring of all planar graphs
    Jelena Sedlar, Riste Škrekovsk
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Degree-truncated DP-colouring of {K4,K2,t}-minor-free graphs
    Huan Zhou
    arXivPreprintCC BY-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Isomorphisms of abelian Cayley graphs with their natural edge-colouring
    Shirin Alimirzaei, Dave Witte Morris
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Strong Edge Colouring of Disk Graphs: A 6-Approximation and an Improved Unit-Disk Bound
    Sandip Das, Sk Samim Islam, Aashirwad Mohapatra +2
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{beaton2026obstructions,
  title = {{Obstructions to $k$-colouring $H$-free graphs}},
  author = {Iain Beaton and Ben Cameron and Adam van Omme},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.10737},
  eprint = {2610.10737},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.10737},
  note = {CC BY-NC-SA 4.0},
}
RIS
TY  - UNPB
TI  - Obstructions to k-colouring H-free graphs
AU  - Iain Beaton
AU  - Ben Cameron
AU  - Adam van Omme
PY  - 2026
DA  - 2026/10/07
PB  - arXiv
DO  - 10.48550/arxiv.2610.10737
UR  - https://arxiv.org/abs/2610.10737
AB  - 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 χ(G)=k+1 but χ(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+ℓ P_1 for some ℓ ≥ 0.
ER  -