Discrete Mathematics & Theoretical Computer Science, Vol 6, No 2 (2004)

Font Size:  Small  Medium  Large

New Results on Generalized Graph Coloring

Vladimir E. Alekseev, Alastair Farrugia, Vadim V. Lozin


For graph classes ℘1,...,℘k, Generalized Graph Coloring is the problem of deciding whether the vertex set of a given graph G can be partitioned into subsets V1,...,Vk so that Vj induces a graph in the class ℘j (j=1,2,...,k). If ℘1=...=℘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 ℘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 ℘i's are co-additive.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page