Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914339468869632 |
|---|---|
| author | Eagling-Vose, Tala Jooken, Jorik Lucke, Felicia Martin, Barnaby Paulusma, Daniël |
| author_facet | Eagling-Vose, Tala Jooken, Jorik Lucke, Felicia Martin, Barnaby Paulusma, Daniël |
| contents | We consider Colouring on graphs that are $H$-subgraph-free for some fixed graph $H$, which are graphs that do not contain $H$ as a subgraph. To classify the complexity of Colouring on $H$-subgraph-free graphs for connected $H$, it remains to consider when $H$ is a 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 $\mathbb{H}_0$: a tree of maximum degree $4$ that is a star, or a subdivided $\mathbb{H}_1$: a tree of maximum degree $3$ with exactly two vertices of degree $3$. We develop new decomposition theorems resulting in polynomial-time algorithms, and in combination with known results, fully classify all cases $\mathbb{H}_0$ and $\mathbb{H}_1$. To illustrate the wider applicability of our techniques, we also employ them to obtain similar new polynomial-time results for two other classic graph problems: Stable Cut and, in part, Feedback Vertex Set. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_09859 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification Eagling-Vose, Tala Jooken, Jorik Lucke, Felicia Martin, Barnaby Paulusma, Daniël Combinatorics Computational Complexity Discrete Mathematics Data Structures and Algorithms We consider Colouring on graphs that are $H$-subgraph-free for some fixed graph $H$, which are graphs that do not contain $H$ as a subgraph. To classify the complexity of Colouring on $H$-subgraph-free graphs for connected $H$, it remains to consider when $H$ is a 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 $\mathbb{H}_0$: a tree of maximum degree $4$ that is a star, or a subdivided $\mathbb{H}_1$: a tree of maximum degree $3$ with exactly two vertices of degree $3$. We develop new decomposition theorems resulting in polynomial-time algorithms, and in combination with known results, fully classify all cases $\mathbb{H}_0$ and $\mathbb{H}_1$. To illustrate the wider applicability of our techniques, we also employ them to obtain similar new polynomial-time results for two other classic graph problems: Stable Cut and, in part, Feedback Vertex Set. |
| title | Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification |
| topic | Combinatorics Computational Complexity Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.09859 |