Fixed-parameter algorithms for the cocoloring problem.

Abstract: A -cocoloring of a graph is a partition of the vertex set of into at most independent sets and at most cliques. It is known that determining the cochromatic number and the split chromatic number, which are respectively the minimum and the minimum such that is -cocolorable, is NP-hard problem. A -graph is a graph such that every subset of at most vertices induces at most distinct ’s. In 2011, Bravo et al. obtained a polynomial time algorithm to decide if a -graph is -cocolorable (Bravo et al., 2011). In this paper, we extend this result by obtaining polynomial time algorithms to decide the -cocolorability and to determine the cochromatic number and the split chromatic number for -graphs for every fixed and for graphs with bounded treewidth. We also obtain a polynomial time algorithm to obtain the maximum -cocolorable subgraph of a -graph for every fixed . All these algorithms are fixed parameter tractable. [Copyright &y& Elsevier]