Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-00959005
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Thursday, March 13, 2014 - 5:05:19 PM
Last modification on : Friday, August 9, 2019 - 3:24:02 PM
Long-term archiving on: : Friday, June 13, 2014 - 12:11:04 PM

File

dm060204.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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

Share

Metrics

Record views

77

Files downloads

592