New results on generalized graph coloring
| dc.creator | Alekseev, Vladimir E. | |
| dc.creator | Farrugia, Alastair | |
| dc.creator | Lozin, Vadim V. | |
| dc.date | 2003-06-10 | |
| dc.date.accessioned | 2026-07-07T04:58:53Z | |
| dc.date.available | 2026-07-07T04:58:53Z | |
| dc.description | 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. | |
| dc.description | 9 pages, 1 figure, submitted to Discrete Mathematics and Theoretical Computer Science | |
| dc.identifier | https://arxiv.org/abs/math/0306178 | |
| dc.identifier | http://arxiv.org/abs/math/0306178 | |
| dc.identifier | DMTCS Volume 6 n. 2 (2004), pp. 215-222 http://dmtcs.loria.fr/volumes/abstracts/dm060204.abs.html | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/67765 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C15 (Primary), 05C85, 68Q17 (Secondary) | |
| dc.title | New results on generalized graph coloring | |
| dc.type | text |