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

Search Results

Documents authored by Zhong, Mingxian

Complexity of C_k-Coloring in Hereditary Classes of Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message