-partition of some classes of graphs

详细信息    查看全文

• 作者：Simone Dantas ; Fr¨¦d¨¦ric Maffray ; Ana Silva
• 关键词：Graph theory ; Complexity ; H-partition problem ; 2K2-partition ; Graph classes
• 刊名：Discrete Applied Mathematics
• 出版年：2012
• 出版时间：December, 2012
• 年：2012
• 卷：160
• 期：18
• 页码：2662-2668
• 全文大小：234 K

文摘

We consider the problem of partitioning the vertex-set of a graph into four non-empty sets such that every vertex of is adjacent to every vertex of and every vertex of is adjacent to every vertex of . The complexity of deciding if a graph admits such a partition is unknown. We show that it can be solved in polynomial time for several classes of graphs: -free graphs, diamond-free graphs, planar graphs, graphs with bounded treewidth, claw-free graphs, -free graphs and graphs with few ¡¯s.