Coloring graphs characterized by a forbidden subgraph
Paulusma, Daniël; Golovach, Petr A.; Ries, Bernard (2015), Coloring graphs characterized by a forbidden subgraph, Discrete Applied Mathematics, 180, p. 101110. 10.1016/j.dam.2014.08.008
Type
Article accepté pour publication ou publiéDate
2015Journal name
Discrete Applied MathematicsVolume
180Publisher
Elsevier
Pages
101110
Publication identifier
Metadata
Show full item recordAuthor(s)
Paulusma, DaniëlGolovach, Petr A.
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 kk colors for some given kk, such that no two adjacent vertices receive the same color. The complexity of this problem on graphs that do not contain some graph HH as an induced subgraph is known for each fixed graph HH. A natural variant is to forbid a graph HH only as a subgraph. We call such graphs strongly HHfree and initiate a complexity classification of Coloring for strongly HHfree graphs. We show that Coloring is NPcomplete for strongly HHfree graphs, even for k=3k=3, when HH contains a cycle, has maximum degree at least 5, or contains a connected component with two vertices of degree 4. We also give three conditions on a forest HH of maximum degree at most 4 and with at most one vertex of degree 4 in each of its connected components, such that Coloring is NPcomplete for strongly HHfree graphs even for k=3k=3. Finally, we classify the computational complexity of Coloring on strongly HHfree graphs for all fixed graphs HH up to seven vertices. In particular, we show that Coloring is polynomialtime solvable when HH is a forest that has at most seven vertices and maximum degree at most 4.Subjects / Keywords
Forbidden subgraphs; Graph coloring; Algorithms; ComplexityRelated items
Showing items related by title and author.

Golovach, Petr A.; Paulusma, Daniël; Ries, Bernard (2012) Communication / Conférence

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

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

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

Ries, Bernard; Pop, Petrica; Monnot, Jérôme; Demange, Marc (2012) Communication / Conférence