Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
427607 | Information Processing Letters | 2012 | 6 Pages |
A (k,ℓ)(k,ℓ)-cocoloring of a graph is a partition of its vertex set into at most k stable sets and at most ℓ cliques. It is known that deciding if a graph is (k,ℓ)(k,ℓ)-cocolorable is NP-complete. A graph is extended P4P4-laden if every induced subgraph with at most six vertices that contains more than two induced P4P4ʼs is {2K2,C4}{2K2,C4}-free. Extended P4P4-laden graphs generalize cographs, P4P4-sparse and P4P4-tidy graphs. In this paper, we obtain a linear time algorithm to decide if, given k,ℓ⩾0k,ℓ⩾0, an extended P4P4-laden graph is (k,ℓ)(k,ℓ)-cocolorable. Consequently, we obtain a polynomial time algorithm to determine the cochromatic number and the split chromatic number of an extended P4P4-laden graph. Finally, we present a polynomial time algorithm to find a maximum induced (k,ℓ)(k,ℓ)-cocolorable subgraph of an extended P4P4-laden graph, generalizing the main results of Bravo et al. (2011) [4] and Demange et al. (2005) [5].
► We obtain a linear time algorithm to decide if, given positive integers k and l , an extended P4P4-laden graph is (k,ℓ)(k,ℓ)-cocolorable. ► We obtain polynomial time algorithms to determine the cochromatic number and the split chromatic number of an extended P4P4-laden graph. ► We present a polynomial time algorithm to find a maximum induced (k,ℓ)(k,ℓ)-cocolorable subgraph of an extended P4P4-laden graph.