The complexity of partitioning into disjoint cliques and a triangle-free graph

详细信息    查看全文

• 作者：Marin Bougeret ; Pascal Ochem ; ^{ochem@lirmm.fr}
• 关键词：Graph coloring ; NP-completeness
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P3
• 页码：438-445
• 全文大小：568 K
• 卷排序：217

文摘

Motivated by Chudnovsky’s structure theorem of bull-free graphs, Abu-Khzam, Feghali, and Müller have recently proved that deciding if a graph has a vertex partition into disjoint cliques and a triangle-free graph is NP-complete for five graph classes. The problem is trivial for the intersection of these five classes. We prove that the problem is NP-complete for the intersection of two subsets of size four among the five classes. We also show NP-completeness for other small classes, such as graphs with maximum degree 4 and line graphs.