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 2731, 2012, Proceedings, Springer : Berlin, p. 443454. 10.1007/9783642325892_40
Type
Communication / ConférenceDate
2012Conference title
37th International Symposium on Mathematical Foundations of Computer Science 2012, MFCS 2012Conference date
201208Conference city
BratislavaConference country
SlovakiaBook title
Mathematical Foundations of Computer Science 2012 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 2731, 2012, ProceedingsBook author
Rovan, Branislav; Sassone, Vladimiro; Widmayer, PeterPublisher
Springer
Series title
Lecture Notes in Computer ScienceSeries number
7464Published in
Berlin
ISBN
9783642325885
Number of pages
825Pages
443454
Publication identifier
Metadata
Show full item recordAuthor(s)
Golovach, Petr A.Department of Mathematics [Bergen] [UiB]
Paulusma, Daniël
School of Engineering and Computing Sciences
Ries, Bernard
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 Hfree and initiate a complexity classification of Coloring for strongly Hfree graphs. We show that Coloring is NPcomplete for strongly Hfree 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 NPcomplete for strongly Hfree graphs even for k = 3. Finally, we classify the computational complexity of Coloring on strongly Hfree graphs for all fixed graphs H up to seven vertices. In particular, we show that Coloring is polynomialtime solvable when H is a forest that has at most seven vertices and maximum degree at most four.Subjects / Keywords
graphs; Coloring problemRelated items
Showing items related by title and author.

Paulusma, Daniël; Golovach, Petr A.; Ries, Bernard (2015) Article accepté pour publication ou publié

Diner, Öznur Yaşar; Paulusma, Daniël; Picouleau, Christophe; Ries, Bernard (2018) Article accepté pour publication ou publié

Paulusma, Daniël; Picouleau, Christophe; Ries, Bernard (2019) Article accepté pour publication ou publié

Ries, Bernard; Picouleau, Christophe; Paulusma, Daniël; Diner, Öznur (2015) Communication / Conférence

Ries, Bernard; Pop, Petrica; Monnot, Jérôme; Demange, Marc (2014) Article accepté pour publication ou publié