Immersion in four-edge-connected graphs

Maria Chudnovsky; Zdeněk Dvořák; Tereza Klimošová; Paul Seymour

doi:10.1016/j.jctb.2015.07.006

Immersion in four-edge-connected graphs

Maria Chudnovsky, Zdeněk Dvořák, Tereza Klimošová, Paul Seymour

Mathematics

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

Fix g > 1. Every graph of large enough tree-width contains a g× g grid as a minor; but here we prove that every four-edge-connected graph of large enough tree-width contains a g× g grid as an immersion (and hence contains any fixed graph with maximum degree at most four as an immersion). This result has a number of applications.

Original language	English (US)
Pages (from-to)	208-218
Number of pages	11
Journal	Journal of Combinatorial Theory. Series B
Volume	116
DOIs	https://doi.org/10.1016/j.jctb.2015.07.006
State	Published - Jan 2016

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Graph immersion
Grid minors

Access to Document

10.1016/j.jctb.2015.07.006

Cite this

@article{8fa0a32d575e4987b66474f56ae0ced6,

title = "Immersion in four-edge-connected graphs",

abstract = "Fix g > 1. Every graph of large enough tree-width contains a g× g grid as a minor; but here we prove that every four-edge-connected graph of large enough tree-width contains a g× g grid as an immersion (and hence contains any fixed graph with maximum degree at most four as an immersion). This result has a number of applications.",

keywords = "Graph immersion, Grid minors",

author = "Maria Chudnovsky and Zden{\v e}k Dvo{\v r}{\'a}k and Tereza Klimo{\v s}ov{\'a} and Paul Seymour",

note = "Publisher Copyright: {\textcopyright} 2015 Elsevier Inc.",

year = "2016",

month = jan,

doi = "10.1016/j.jctb.2015.07.006",

language = "English (US)",

volume = "116",

pages = "208--218",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Immersion in four-edge-connected graphs

AU - Chudnovsky, Maria

AU - Dvořák, Zdeněk

AU - Klimošová, Tereza

AU - Seymour, Paul

PY - 2016/1

Y1 - 2016/1

N2 - Fix g > 1. Every graph of large enough tree-width contains a g× g grid as a minor; but here we prove that every four-edge-connected graph of large enough tree-width contains a g× g grid as an immersion (and hence contains any fixed graph with maximum degree at most four as an immersion). This result has a number of applications.

AB - Fix g > 1. Every graph of large enough tree-width contains a g× g grid as a minor; but here we prove that every four-edge-connected graph of large enough tree-width contains a g× g grid as an immersion (and hence contains any fixed graph with maximum degree at most four as an immersion). This result has a number of applications.

KW - Graph immersion

KW - Grid minors

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

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

U2 - 10.1016/j.jctb.2015.07.006

DO - 10.1016/j.jctb.2015.07.006

M3 - Article

AN - SCOPUS:84947618027

SN - 0095-8956

VL - 116

SP - 208

EP - 218

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Immersion in four-edge-connected graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this