Name
Title | ||
|---|---|---|
The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem |
Abstract | ||
|---|---|---|
The graph sandwich problem asks, for a pair of graphs G 1 = ( V , E 1 ) and G 2 = ( V , E 2 ) with E 1 E 2 , whether there exists a graph G = ( V , E ) that satisfies property and E 1 E E 2 . We consider the property of being F -free, where F is a fixed graph. We show that the claw-free graph sandwich and the bull-free graph sandwich problems are both NP-complete, but the paw-free graph sandwich problem is polynomial. This completes the study of all cases where F has at most four vertices. A skew partition of a graph G is a partition of its vertex set into four nonempty parts A , B , C , D such that each vertex of A is adjacent to each vertex of B , and each vertex of C is nonadjacent to each vertex of D . We prove that the skew partition sandwich problem is NP-complete, establishing a computational complexity non-monotonicity. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.dam.2013.09.004 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Graph sandwich problem,Forbidden subgraph,Perfect graphs | Skew partition,Discrete mathematics,Circulant graph,Combinatorics,Vertex (graph theory),Cycle graph,Neighbourhood (graph theory),Regular graph,Mathematics,Feedback vertex set,Graph sandwich problem | Journal |
Volume | Issue | ISSN |
182 | C | 0166-218X |
Citations | PageRank | References |
1 | 0.36 | 21 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Simone Dantas | 1 | 119 | 24.99 |
| Celina M.H. de Figueiredo | 2 | 45 | 5.65 |
| Frédéric Maffray | 3 | 589 | 81.22 |
| Rafael B. Teixeira | 4 | 49 | 5.31 |