Name
Abstract | ||
|---|---|---|
A cograph is a graph that contains no path on four vertices as an induced subgraph. A cographk-partition of a graph G = (V,E) is a vertex partition of G into k sets V-1, ..., V-k < subset of> V so that the graph induced by V-i is a cograph for 1 i k. Gimbel and Neetil [5] studied the complexity aspects of the cograph k-partitions and raised the following questions: Does there exist a triangle-free planar graph that is not cograph 2-partitionable? If the answer is yes, what is the complexity of the associated decision problem? In this article, we prove that such an example exists and that deciding whether a triangle-free planar graph admits a cograph 2-partition is NP-complete. We also show that every graph with maximum average degree at most ??? admits a cograph 2-partition such that each component is a star on at most three vertices. (C) 2013 Wiley Periodicals, Inc. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1002/jgt.21724 | JOURNAL OF GRAPH THEORY |
Keywords | Field | DocType |
cograph partition,colorings,NP-completeness | Topology,Discrete mathematics,Combinatorics,Modular decomposition,Decision problem,Vertex (geometry),Stars,Induced subgraph,Cograph,Planar graph,Mathematics,A* search algorithm | Journal |
Volume | Issue | ISSN |
75.0 | 1.0 | 0364-9024 |
Citations | PageRank | References |
3 | 0.43 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul Dorbec | 1 | 176 | 20.24 |
| Mickaël Montassier | 2 | 288 | 28.20 |
| Pascal Ochem | 3 | 258 | 36.91 |