Fixed-parameter algorithms for the cocoloring problem

A (k,ℓ)(k,ℓ)-cocoloring of a graph GG is a partition of the vertex set of GG into at most kk independent sets and at most ℓℓ cliques. It is known that determining the cochromatic number and the split chromatic number, which are respectively the minimum k+ℓk+ℓ and the minimum max{k,ℓ}max{k,ℓ} such that GG is (k,ℓ)(k,ℓ)-cocolorable, is NP-hard problem. A (q,q−4)(q,q−4)-graph is a graph such that every subset of at most qq vertices induces at most q−4q−4 distinct P4P4’s. In 2011, Bravo et al. obtained a polynomial time algorithm to decide if a (5,1)(5,1)-graph is (k,ℓ)(k,ℓ)-cocolorable (Bravo et al., 2011). In this paper, we extend this result by obtaining polynomial time algorithms to decide the (k,ℓ)(k,ℓ)-cocolorability and to determine the cochromatic number and the split chromatic number for (q,q−4)(q,q−4)-graphs for every fixed qq and for graphs with bounded treewidth. We also obtain a polynomial time algorithm to obtain the maximum (k,ℓ)(k,ℓ)-cocolorable subgraph of a (q,q−4)(q,q−4)-graph for every fixed qq. All these algorithms are fixed parameter tractable.