K4-minor-free induced subgraphs of sparse connected graphs

Gwenaël Joret; David R. Wood

doi:10.1137/16M107712X

K₄-minor-free induced subgraphs of sparse connected graphs

Gwenaël Joret, David R. Wood

School of Mathematics

Research output: Contribution to journal › Article › Research › peer-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 K₄ 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	https://doi.org/10.1137/16M107712X
Publication status	Published - 1 Jan 2018

Keywords

K4-minor
Series-parallel
Transversal

Access to Document

10.1137/16M107712X

Cite this

@article{f98c95886a624e458fe6d4be115b9ed0,

title = "K4-minor-free induced subgraphs of sparse connected graphs",

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.",

keywords = "K4-minor, Series-parallel, Transversal",

author = "Gwena{\"e}l Joret and Wood, {David R.}",

year = "2018",

month = jan,

day = "1",

doi = "10.1137/16M107712X",

language = "English",

volume = "32",

pages = "123--147",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial & Applied Mathematics (SIAM)",

number = "1",

}

TY - JOUR

T1 - K4-minor-free induced subgraphs of sparse connected graphs

AU - Joret, Gwenaël

AU - Wood, David R.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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.

AB - 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.

KW - K4-minor

KW - Series-parallel

KW - Transversal

UR - http://www.scopus.com/inward/record.url?scp=85045640187&partnerID=8YFLogxK

U2 - 10.1137/16M107712X

DO - 10.1137/16M107712X

M3 - Article

AN - SCOPUS:85045640187

VL - 32

SP - 123

EP - 147

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

SN - 0895-4801

IS - 1