DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2019.31

Complexity of C_k-Coloring in Hereditary Classes of Graphs

Authors: Maria Chudnovsky, Shenwei Huang, Paweł Rzążewski, Sophie Spirkl, and Mingxian Zhong

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

Abstract

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.

Cite as

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

DOI: 10.4230/LIPIcs.STACS.2018.35

Colouring Square-Free Graphs without Long Induced Paths

Authors: Serge Gaspers, Shenwei Huang, and Daniel Paulusma

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

Abstract

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.

Cite as

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}
}

Search Results

Documents authored by Huang, Shenwei

Complexity of C_k-Coloring in Hereditary Classes of Graphs

Abstract

Cite as

Colouring Square-Free Graphs without Long Induced Paths

Abstract

Cite as

Thanks for your feedback!

Could not send message