Coloring Graphs Characterized by a Forbidden Subgraph
Golovach, Petr A.; Paulusma, Daniël; Ries, Bernard (2012), Coloring Graphs Characterized by a Forbidden Subgraph, in Rovan, Branislav; Sassone, Vladimiro; Widmayer, Peter, Mathematical Foundations of Computer Science 2012 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012, Proceedings, Springer : Berlin, p. 443-454. 10.1007/978-3-642-32589-2_40
TypeCommunication / Conférence
Conference title37th International Symposium on Mathematical Foundations of Computer Science 2012, MFCS 2012
Book titleMathematical Foundations of Computer Science 2012 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012, Proceedings
Book authorRovan, Branislav; Sassone, Vladimiro; Widmayer, Peter
Series titleLecture Notes in Computer Science
Number of pages825
MetadataShow full item record
Author(s)Golovach, Petr A.
Department of Mathematics [Bergen] [UiB]
School of Engineering and Computing Sciences
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)The Coloring problem is to test whether a given graph can be colored with at most k colors for some given k, such that no two adjacent vertices receive the same color. The complexity of this problem on graphs that do not contain some graph H as an induced subgraph is known for each fixed graph H. A natural variant is to forbid a graph H only as a subgraph. We call such graphs strongly H-free and initiate a complexity classification of Coloring for strongly H-free graphs. We show that Coloring is NP-complete for strongly H-free graphs, even for k = 3, when H contains a cycle, has maximum degree at least five, or contains a connected component with two vertices of degree four. We also give three conditions on a forest H of maximum degree at most four and with at most one vertex of degree four in each of its connected components, such that Coloring is NP-complete for strongly H-free graphs even for k = 3. Finally, we classify the computational complexity of Coloring on strongly H-free graphs for all fixed graphs H up to seven vertices. In particular, we show that Coloring is polynomial-time solvable when H is a forest that has at most seven vertices and maximum degree at most four.
Subjects / Keywordsgraphs; Coloring problem
Showing items related by title and author.
Ries, Bernard; Pop, Petrica; Monnot, Jérôme; Demange, Marc (2014) Article accepté pour publication ou publié