New Results on Generalized Graph Coloring

Abstract : For graph classes \wp_1,...,\wp_k, Generalized Graph Coloring is the problem of deciding whether the vertex set of a given graph G can be partitioned into subsets V_1,...,V_k so that V_j induces a graph in the class \wp_j (j=1,2,...,k). If \wp_1=...=\wp_k is the class of edgeless graphs, then this problem coincides with the standard vertex k-COLORABILITY, which is known to be NP-complete for any k≥ 3. Recently, this result has been generalized by showing that if all \wp_i's are additive hereditary, then the generalized graph coloring is NP-hard, with the only exception of bipartite graphs. Clearly, a similar result follows when all the \wp_i's are co-additive.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2004, 6 (2), pp.215-222
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00959005
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 13 mars 2014 - 17:05:19
Dernière modification le : mercredi 29 novembre 2017 - 10:26:24
Document(s) archivé(s) le : vendredi 13 juin 2014 - 12:11:04

Fichier

dm060204.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00959005, version 1

Collections

Citation

Vladimir E. Alekseev, Alastair Farrugia, Vadim V. Lozin. New Results on Generalized Graph Coloring. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2004, 6 (2), pp.215-222. 〈hal-00959005〉

Partager

Métriques

Consultations de la notice

127

Téléchargements de fichiers

228