Partitioning extended -laden graphs into cliques and stable sets

详细信息    查看全文

• 作者：Raquel S.F. Bravo ; Sulamita Klein ; Loana T. Nogueira ; F¨¢bio Protti ; Rudini M. Sampaio
• 关键词：Graph algorithms ; Graph partition ; (k ; ?)-graphs ; P4-laden graphs ; (k ; ?)-cocoloring
• 刊名：Information Processing Letters
• 出版年：2012
• 出版时间：15 November, 2012
• 年：2012
• 卷：112
• 期：21
• 页码：829-834
• 全文大小：178 K

文摘

A -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 -cocolorable is NP-complete. A graph is extended -laden if every induced subgraph with at most six vertices that contains more than two induced ?s is -free. Extended -laden graphs generalize cographs, -sparse and -tidy graphs. In this paper, we obtain a linear time algorithm to decide if, given , an extended -laden graph is -cocolorable. Consequently, we obtain a polynomial time algorithm to determine the cochromatic number and the split chromatic number of an extended -laden graph. Finally, we present a polynomial time algorithm to find a maximum induced -cocolorable subgraph of an extended -laden graph, generalizing the main results of Bravo et al. (2011) and Demange et al. (2005) .