Vladimir E. Alekseev ; Alastair Farrugia ; Vadim V. Lozin - New Results on Generalized Graph Coloring

dmtcs:311 - Discrete Mathematics & Theoretical Computer Science, January 1, 2004, Vol. 6 no. 2 - https://doi.org/10.46298/dmtcs.311
New Results on Generalized Graph ColoringArticle

Authors: Vladimir E. Alekseev ORCID1; Alastair Farrugia 2; Vadim V. Lozin ORCID3

  • 1 Department of Mathematical Logic [Novgorod]
  • 2 Department of Combinatorics and Optimization
  • 3 Rutgers Center for Operations Research

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.


Volume: Vol. 6 no. 2
Published on: January 1, 2004
Imported on: March 26, 2015
Keywords: Generalized Graph Coloring,Polynomial algorithm,NP-completeness,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Consultation statistics

This page has been seen 276 times.
This article's PDF has been downloaded 251 times.