Skip to main content

Research Repository

Advanced Search

Coloring graphs characterized by a forbidden subgraph

Golovach, P. A. ; Paulusma, D.; Ries, B.

Authors

P. A. Golovach

B. Ries



Contributors

Branislav Rovan
Editor

Vladimiro Sassone
Editor

Peter Widmayer
Editor

Abstract

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.

Citation

Golovach, P. A., Paulusma, D., & Ries, B. (2012). Coloring graphs characterized by a forbidden subgraph. In B. Rovan, V. Sassone, & P. Widmayer (Eds.), Mathematical foundations of computer science 2012 : 37th International Symposium, MFCS 2012, Bratislava, Slovakia, 27-31 August 2012 ; proceedings (443-454). https://doi.org/10.1007/978-3-642-32589-2_40

Publication Date 2012
Deposit Date Mar 11, 2013
Volume 7464
Pages 443-454
Series Title Lecture notes in computer science
Series Number 7464
Series ISSN 0302-9743,1611-3349
Book Title Mathematical foundations of computer science 2012 : 37th International Symposium, MFCS 2012, Bratislava, Slovakia, 27-31 August 2012 ; proceedings.
ISBN 9783642325885
DOI https://doi.org/10.1007/978-3-642-32589-2_40
Public URL https://durham-repository.worktribe.com/output/1156276
Additional Information Series: Lecture Notes in Computer Science, Volume 7464


You might also like



Downloadable Citations