Name
Abstract | ||
|---|---|---|
We prove that every connected graph G with m edges contains a set X of at most 3/16(m + 1) vertices such that G-X has no K-4 minor, or, equivalently, has treewidth at most 2. This bound is best possible. Connectivity is essential: If G is not connected, then only a bound of 1/5m can be guaranteed. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1137/16M107712X | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
K-4-minor,series-parallel,transversal | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Transversal (geometry),Treewidth,Series and parallel circuits,Connectivity,Mathematics | Journal |
Volume | Issue | ISSN |
32 | 1 | 0895-4801 |
Citations | PageRank | References |
0 | 0.34 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gwenaël Joret | 1 | 196 | 28.64 |
| David R. Wood | 2 | 1073 | 96.22 |