• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Coloring Graphs Characterized by a Forbidden Subgraph

Thumbnail
Date
2012
Collection title
Lecture Notes in Computer Science
Collection Id
7464
Dewey
Intelligence artificielle
Sujet
graphs; Coloring problem
DOI
http://dx.doi.org/10.1007/978-3-642-32589-2_40
Conference name
37th International Symposium on Mathematical Foundations of Computer Science 2012, MFCS 2012
Conference date
08-2012
Conference city
Bratislava
Conference country
Slovakia
Book title
Mathematical Foundations of Computer Science 2012 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012, Proceedings
Author
Rovan, Branislav; Sassone, Vladimiro; Widmayer, Peter
Publisher
Springer
Publisher city
Berlin
Year
2012
Pages number
825
ISBN
978-3-642-32588-5
Book URL
http://dx.doi.org/10.1007/978-3-642-32589-2
URI
https://basepub.dauphine.fr/handle/123456789/11643
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Golovach, Petr A.
status unknown
Paulusma, Daniël
184027 School of Engineering and Computing Sciences
Ries, Bernard
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Communication / Conférence
Item number of pages
443-454
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.