Name
Abstract | ||
|---|---|---|
We consider the problem of partitioning the vertex-set of a graph into four non-empty sets A,B,C,D such that every vertex of A is adjacent to every vertex of B and every vertex of C is adjacent to every vertex of D. 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: K"4-free graphs, diamond-free graphs, planar graphs, graphs with bounded treewidth, claw-free graphs, (C"5,P"5)-free graphs and graphs with few P"4's. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.dam.2010.09.009 | Discrete Applied Mathematics |
Keywords | DocType | Volume |
bounded treewidth,4-free graph,Complexity,planar graph,Graph theory,polynomial time,free graph,2 K 2 -partition,claw-free graph,H -partition problem,diamond-free graph,Graph classes | Journal | 160 |
Issue | ISSN | Citations |
18 | Discrete Applied Mathematics | 4 |
PageRank | References | Authors |
0.40 | 9 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Simone Dantas | 1 | 119 | 24.99 |
| Frédéric Maffray | 2 | 589 | 81.22 |
| Ana Silva | 3 | 27 | 4.74 |