2025/12/10 by Eagling-Vose, Tala, Jooken, Jorik, Lucke, Felicia +2
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2512.09859
We consider Colouring on graphs that are H-subgraph-free for some fixed graph H, i.e., graphs that do not contain H as a subgraph. It is known that even 3-Colouring is NP-complete for H-subgraph-free graphs whenever H has a cycle; or a vertex of degree at least 5; or a component with two vertices of degree 4, while Colouring is polynomial-time solvable for H-subgraph-free graphs if H is a forest of maximum degree at most 3, in which each component has at most one vertex of degree 3. For connected graphs H, this means that it remains to consider when H is tree of maximum degree 4 with exactly one vertex of degree 4, or a tree of maximum degree 3 with at least two vertices of degree 3. We let H be a so-called subdivided "H"-graph, which is either a subdivided ℍ0: a tree of maximum degree 4 with exactly one vertex of degree 4 and no vertices of degree 3, or a subdivided ℍ1: a tree of maximum degree 3 with exactly two vertices of degree 3. In the literature, only a limited number of polynomial-time and NP-completeness results for these cases are known. We develop new polynomial-time techniques that allow us to determine the complexity of Colouring on H-subgraph-free graphs for all the remaining subdivided "H"-graphs, so we fully classify both cases. As a consequence, the complexity of Colouring on H-subgraph-free graphs has now been settled for all connected graphs H except when H is a tree of maximum degree 4 with exactly one vertex of degree 4 and at least one vertex of degree 3; or a tree of maximum degree 3 with at least three vertices of degree 3. We also employ our new techniques to obtain the same new polynomial-time results for another classic graph problem, namely Stable Cut.