Back to Search
Start Over
New Results on Generalized Graph Coloring.
- Source :
-
Discrete Mathematics & Theoretical Computer Science (DMTCS) . Jun2004, Vol. 7 Issue 1, p215-221. 7p. 1 Diagram. - Publication Year :
- 2004
-
Abstract
- For graph classes P1, . . . , Pk, 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 Pj ( j = 1, 2, . . . , k). If P1 = ... = Pk 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 Pi'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 Pi's are co-additive. In this paper, we study the problem where we have a mixture of additive and co-additive classes, presenting several new results dealing both with NP-hard and polynomial-time solvable instances of the problem. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GRAPH coloring
*GRAPH theory
*GRAPHIC methods
*POLYNOMIALS
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 13658050
- Volume :
- 7
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics & Theoretical Computer Science (DMTCS)
- Publication Type :
- Academic Journal
- Accession number :
- 13537409