DROPS

Document

DOI: 10.4230/LIPIcs.WG.2026.16

Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification

Authors: Tala Eagling-Vose, Jorik Jooken, Felicia Lucke, Barnaby Martin, and Daniël Paulusma

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

Abstract

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 ℍ₀: a tree of maximum degree 4 that is a star, or a subdivided ℍ₁: 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 ℍ₀ and ℍ₁. 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.

Cite as

Tala Eagling-Vose, Jorik Jooken, Felicia Lucke, Barnaby Martin, and Daniël Paulusma. Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{eaglingvose_et_al:LIPIcs.WG.2026.16,
  author =	{Eagling-Vose, Tala and Jooken, Jorik and Lucke, Felicia and Martin, Barnaby and Paulusma, Dani\"{e}l},
  title =	{{Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.16},
  URN =		{urn:nbn:de:0030-drops-261827},
  doi =		{10.4230/LIPIcs.WG.2026.16},
  annote =	{Keywords: colouring, forbidden subgraph, complexity dichotomy}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2024.55

Minimal Obstructions to C₅-Coloring in Hereditary Graph Classes

Authors: Jan Goedgebeur, Jorik Jooken, Karolina Okrasa, Paweł Rzążewski, and Oliver Schaudt

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract

For graphs G and H, an H-coloring of G is an edge-preserving mapping from V(G) to V(H). Note that if H is the triangle, then H-colorings are equivalent to 3-colorings. In this paper we are interested in the case that H is the five-vertex cycle C₅. A minimal obstruction to C₅-coloring is a graph that does not have a C₅-coloring, but every proper induced subgraph thereof has a C₅-coloring. In this paper we are interested in minimal obstructions to C₅-coloring in F-free graphs, i.e., graphs that exclude some fixed graph F as an induced subgraph. Let P_t denote the path on t vertices, and let S_{a,b,c} denote the graph obtained from paths P_{a+1},P_{b+1},P_{c+1} by identifying one of their endvertices. We show that there is only a finite number of minimal obstructions to C₅-coloring among F-free graphs, where F ∈ {P₈, S_{2,2,1}, S_{3,1,1}} and explicitly determine all such obstructions. This extends the results of Kamiński and Pstrucha [Discr. Appl. Math. 261, 2019] who proved that there is only a finite number of P₇-free minimal obstructions to C₅-coloring, and of Dębski et al. [ISAAC 2022 Proc.] who showed that the triangle is the unique S_{2,1,1}-free minimal obstruction to C₅-coloring. We complement our results with a construction of an infinite family of minimal obstructions to C₅-coloring, which are simultaneously P_{13}-free and S_{2,2,2}-free. We also discuss infinite families of F-free minimal obstructions to H-coloring for other graphs H.

Cite as

Jan Goedgebeur, Jorik Jooken, Karolina Okrasa, Paweł Rzążewski, and Oliver Schaudt. Minimal Obstructions to C₅-Coloring in Hereditary Graph Classes. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{goedgebeur_et_al:LIPIcs.MFCS.2024.55,
  author =	{Goedgebeur, Jan and Jooken, Jorik and Okrasa, Karolina and Rz\k{a}\.{z}ewski, Pawe{\l} and Schaudt, Oliver},
  title =	{{Minimal Obstructions to C₅-Coloring in Hereditary Graph Classes}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{55:1--55:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.55},
  URN =		{urn:nbn:de:0030-drops-206110},
  doi =		{10.4230/LIPIcs.MFCS.2024.55},
  annote =	{Keywords: graph homomorphism, critical graphs, hereditary graph classes}
}

Search Results

Documents authored by Jooken, Jorik

Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification

Abstract

Cite as

Minimal Obstructions to C₅-Coloring in Hereditary Graph Classes

Abstract

Cite as

Thanks for your feedback!

Could not send message