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 K4 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/5 m can be guaranteed.
Original language | English |
---|---|
Pages (from-to) | 123-147 |
Number of pages | 25 |
Journal | SIAM Journal on Discrete Mathematics |
Volume | 32 |
Issue number | 1 |
DOIs | |
Publication status | Published - 1 Jan 2018 |
Keywords
- K4-minor
- Series-parallel
- Transversal