Loading...
Please wait, while we are loading the content...
Similar Documents
New results on generalized graph coloring
| Content Provider | arXiv |
|---|---|
| Author | Alekseev, Vladimir E. Farrugia, Alastair Lozin, Vadim V. |
| Date of Submission | 2003-06-10 |
| Abstract | 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. |
| Related Links | https://arxiv.org/pdf/math/0306178.pdf |
| Page Count | 9 |
| arXiv | math/0306178 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Mathematics Graph algorithms Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) Mathematics - Combinatorics Coloring of graphs and hypergraphs |
| Content Type | Text |
| Resource Type | Article |
| Subject | Mathematics |
