Alekseev, Vladimir E.; Farrugia, Alastair; Lozin, Vadim V. New results on generalized graph coloring. (English) Zbl 1059.05044 Discrete Math. Theor. Comput. Sci. 6, No. 2, 215-221 (2004). Summary: For graph classes \({\mathcal P}_1,\dots,{\mathcal 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},\dots,V_{k}\) so that \(V_{j}\) induces a graph in the class \({\mathcal P}_j\) \((j=1,2,\dots,k)\). If \({\mathcal P}_1=\cdots={\mathcal P}_k\) 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\geq 3}\)}. Recently, this result has been generalized by showing that if all \({\mathcal P}_i\)’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 \({\mathcal 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. Cited in 6 Documents MSC: 05C15 Coloring of graphs and hypergraphs 05C85 Graph algorithms (graph-theoretic aspects) 68Q25 Analysis of algorithms and problem complexity 68R10 Graph theory (including graph drawing) in computer science Keywords:Generalized graph coloring; Polynomial algorithm; NP-completeness PDFBibTeX XMLCite \textit{V. E. Alekseev} et al., Discrete Math. Theor. Comput. Sci. 6, No. 2, 215--221 (2004; Zbl 1059.05044) Full Text: arXiv EuDML EMIS