• 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
2015
Dewey
Inteligence artificielle
Sujet
Forbidden subgraphs; Graph coloring; Algorithms; Complexity
Journal issue
Discrete Applied Mathematics
Volume
180
Publication date
2015
Article pages
101-110
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.dam.2014.08.008
URI
https://basepub.dauphine.fr/handle/123456789/13964
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Paulusma, Daniël
status unknown
Golovach, Petr A.
status unknown
Ries, Bernard
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Article accepté pour publication ou publié
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 HH-free and initiate a complexity classification of Coloring for strongly HH-free graphs. We show that Coloring is NP-complete for strongly HH-free 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 NP-complete for strongly HH-free graphs even for k=3k=3. Finally, we classify the computational complexity of Coloring on strongly HH-free graphs for all fixed graphs HH up to seven vertices. In particular, we show that Coloring is polynomial-time solvable when HH is a forest that has at most seven vertices and maximum degree at most 4.

  • 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.