Document

**Published in:** LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

For a graph F, a graph G is F-free if it does not contain an induced subgraph isomorphic to F. For two graphs G and H, an H-coloring of G is a mapping f:V(G) -> V(H) such that for every edge uv in E(G) it holds that f(u)f(v)in E(H). We are interested in the complexity of the problem H-Coloring, which asks for the existence of an H-coloring of an input graph G. In particular, we consider H-Coloring of F-free graphs, where F is a fixed graph and H is an odd cycle of length at least 5. This problem is closely related to the well known open problem of determining the complexity of 3-Coloring of P_t-free graphs.
We show that for every odd k >= 5 the C_k-Coloring problem, even in the precoloring-extension variant, can be solved in polynomial time in P_9-free graphs. On the other hand, we prove that the extension version of C_k-Coloring is NP-complete for F-free graphs whenever some component of F is not a subgraph of a subdivided claw.

Maria Chudnovsky, Shenwei Huang, Paweł Rzążewski, Sophie Spirkl, and Mingxian Zhong. Complexity of C_k-Coloring in Hereditary Classes of Graphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 31:1-31:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chudnovsky_et_al:LIPIcs.ESA.2019.31, author = {Chudnovsky, Maria and Huang, Shenwei and Rz\k{a}\.{z}ewski, Pawe{\l} and Spirkl, Sophie and Zhong, Mingxian}, title = {{Complexity of C\underlinek-Coloring in Hereditary Classes of Graphs}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {31:1--31:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.31}, URN = {urn:nbn:de:0030-drops-111529}, doi = {10.4230/LIPIcs.ESA.2019.31}, annote = {Keywords: homomorphism, hereditary class, computational complexity, forbidden induced subgraph} }

Document

**Published in:** LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

The Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for a given integer k such that no two adjacent vertices are coloured alike. The complexity of Colouring is fully understood for graph classes characterized by one forbidden induced subgraph H. Despite a huge body of existing work, there are still major complexity gaps if two induced subgraphs H_1 and H_2 are forbidden. We let H_1 be the s-vertex cycle C_s and H_2 be the t-vertex path P_t. We show that Colouring is polynomial-time solvable for s=4 and t<=6, which unifies several known results for Colouring on (H_1,H_2)-free graphs. Our algorithm is based on a novel decomposition theorem for (C_4,P_6)-free graphs without clique cutsets into homogeneous pairs of sets and a new framework for bounding the clique-width of a graph by the clique-width of its subgraphs induced by homogeneous pairs of sets. To apply this framework, we also need to use divide-and-conquer to bound the clique-width of subgraphs induced by homogeneous pairs of sets. To complement our positive result we also prove that Colouring is NP-complete for s=4 and t>=9, which is the first hardness result on Colouring for (C_4,P_t)-free graphs.

Serge Gaspers, Shenwei Huang, and Daniel Paulusma. Colouring Square-Free Graphs without Long Induced Paths. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gaspers_et_al:LIPIcs.STACS.2018.35, author = {Gaspers, Serge and Huang, Shenwei and Paulusma, Daniel}, title = {{Colouring Square-Free Graphs without Long Induced Paths}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {35:1--35:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.35}, URN = {urn:nbn:de:0030-drops-84922}, doi = {10.4230/LIPIcs.STACS.2018.35}, annote = {Keywords: graph colouring, hereditary graph class, clique-width, cycle, path} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail