{
  "id": "math/0306178",
  "version": "v1",
  "published": "2003-06-10T20:05:05.000Z",
  "updated": "2003-06-10T20:05:05.000Z",
  "title": "New results on generalized graph coloring",
  "authors": [
    "Vladimir E. Alekseev",
    "Alastair Farrugia",
    "Vadim V. Lozin"
  ],
  "comment": "9 pages, 1 figure, submitted to Discrete Mathematics and Theoretical Computer Science",
  "journal": "DMTCS Volume 6 n. 2 (2004), pp. 215-222 http://dmtcs.loria.fr/volumes/abstracts/dm060204.abs.html",
  "categories": [
    "math.CO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2003-06-10T20:05:05.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C85",
      "68Q17"
    ],
    "keywords": [
      "generalized graph coloring",
      "vertex set",
      "graph classes",
      "problem coincides",
      "standard vertex"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 9,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2003math......6178A"
    }
  }
}