K4-minor-free induced subgraphs of sparse connected graphs

Gwenaël Joret, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review

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 languageEnglish
Pages (from-to)123-147
Number of pages25
JournalSIAM Journal on Discrete Mathematics
Volume32
Issue number1
DOIs
Publication statusPublished - 1 Jan 2018

Keywords

  • K4-minor
  • Series-parallel
  • Transversal

Cite this