Finite obstructions for colouring certain restricted graphs characterized
Obstructions to $k$-colouring $H$-free graphs
Discrete Mathematics
Summary
The problem is about coloring graphs with a limited set of colors without certain forbidden patterns called induced subgraphs. The authors build on previous work that identified when only a few minimal tricky graphs appear for coloring with three colors. They extended this to any number of colors greater than four, fully describing which forbidden patterns lead to only a finite number of minimal hard-to-color graphs. This helps understand exactly which graph restrictions yield manageable coloring challenges.
What this means in practice
- •For graph algorithm designers: Decide when limited graph coloring obstructions are finite to optimize coloring algorithm development for restricted graph classes.
- •For network schedulers: Identify communication scenarios that avoid complex coloring conflicts by recognizing finite obstruction graph classes.
A theory result. No direct application yet.
Authors
Iain Beaton, Ben Cameron, Adam van Omme
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 $P_4+\ell P_1$ for some $\ell \geq 0$.