New Results on Generalized Graph Coloring - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2004

New Results on Generalized Graph Coloring

Résumé

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.
Fichier principal
Vignette du fichier
dm060204.pdf (65.82 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00959005 , version 1 (13-03-2014)

Identifiants

Citer

Vladimir E. Alekseev, Alastair Farrugia, Vadim V. Lozin. New Results on Generalized Graph Coloring. Discrete Mathematics and Theoretical Computer Science, 2004, Vol. 6 no. 2 (2), pp.215-222. ⟨10.46298/dmtcs.311⟩. ⟨hal-00959005⟩

Collections

TDS-MACS
79 Consultations
756 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More