2026-08-17T21:17:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20611 2024-08-23T05:50:29Z ddc:004 open_access

Minimal Obstructions to C₅-Coloring in Hereditary Graph Classes Goedgebeur, Jan Jooken, Jorik Okrasa, Karolina Rzążewski, Paweł Schaudt, Oliver graph homomorphism critical graphs hereditary graph classes 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jan Goedgebeur and Jorik Jooken and Karolina Okrasa and Paweł Rzążewski and Oliver Schaudt 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.55 urn:nbn:de:0030-drops-206110 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.55 eng https://creativecommons.org/licenses/by/4.0/legalcode