New results on generalized graph coloring

Details New results on generalized graph coloring New results on generalized graph coloring

2003-06-10

arxiv.org/abs/math/0306178v1

DMTCS Volume 6 n. 2 (2004), pp. 215-222 http://dmtcs.loria.fr/volumes/abstracts/dm060204.abs.html

Mathematics

Combinatorics

9 pages, 1 figure, submitted to Discrete Mathematics and Theoretical Computer Science

Scientific paper

For graph classes $P_1,...,P_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 $P_j$ $(j=1,2,...,k)$. If $P_1 = ... = P_k$ is the class of edgeless graphs, then this problem coincides with the standard vertex $k$-{\sc colorability}, which is known to be NP-complete for any $k\ge 3$. Recently, this result has been generalized by showing that if all $P_i$'s are additive induced-hereditary, then generalized graph coloring is NP-hard, with the only exception of recognising bipartite graphs. Clearly, a similar result follows when all the $P_i$'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.

Affiliated with

Also associated with

No associations

Rating

New results on generalized graph coloring does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with New results on generalized graph coloring, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and New results on generalized graph coloring will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-458582