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

Afficher

Cette collectionPar Date de CréationAuteursTitresSujetsNoms de revueToute la baseCentres de recherche & CollectionsPar Date de CréationAuteursTitresSujetsNoms de revue

Mon compte

Connexion

Statistiques

Afficher les statistiques d'usage

Coloring graphs characterized by a forbidden subgraph

Thumbnail
Date
2015
Indexation documentaire
Inteligence artificielle
Subject
Forbidden subgraphs; Graph coloring; Algorithms; Complexity
Nom de la revue
Discrete Applied Mathematics
Volume
180
Date de publication
2015
Pages article
101-110
Nom de l'éditeur
Elsevier
DOI
http://dx.doi.org/10.1016/j.dam.2014.08.008
URI
https://basepub.dauphine.fr/handle/123456789/13964
Collections
  • LAMSADE : Publications
Métadonnées
Afficher la notice complète
Auteur
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é
Résumé en anglais
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

 Cette création est mise à disposition sous un contrat Creative Commons.