Forbidding Kuratowski graphs as immersions

Archontia C. Giannopoulou; Marcin Kamiński; Dimitrios M. Thilikos

doi:10.1002/jgt.21790

Forbidding Kuratowski graphs as immersions

Archontia C. Giannopoulou, Marcin Kamiński, Dimitrios M. Thilikos

Computer Science

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

Abstract

Immersion is a containment relation on graphs that is weaker than topological minor. (Every topological minor of a graph is also its immersion.) The graphs that do not contain any of the Kuratowski graphs (K₅ and K_3,3) as topological minors are exactly planar graphs. We give a structural characterization of graphs that exclude the Kuratowski graphs as immersions. We prove that they can be constructed from planar graphs that are subcubic or of branch-width at most 10 by repetitively applying i-edge-sums, for i ∈ {1, 2, 3}. We also use this result to give a structural characterization of graphs that exclude K_3,3 as an immersion.

Original language	English (US)
Pages (from-to)	43-60
Number of pages	18
Journal	Journal of Graph Theory
Volume	78
Issue number	1
DOIs	https://doi.org/10.1002/jgt.21790
State	Published - Jan 1 2015

Keywords

Branch-width
Graph immersions
Kuratowski graphs
Tree-width

ASJC Scopus subject areas

Geometry and Topology

Access to Document

10.1002/jgt.21790

Cite this

@article{31d68589e60b4d76b1be9d2d100dee1e,

title = "Forbidding Kuratowski graphs as immersions",

abstract = "Immersion is a containment relation on graphs that is weaker than topological minor. (Every topological minor of a graph is also its immersion.) The graphs that do not contain any of the Kuratowski graphs (K5 and K3,3) as topological minors are exactly planar graphs. We give a structural characterization of graphs that exclude the Kuratowski graphs as immersions. We prove that they can be constructed from planar graphs that are subcubic or of branch-width at most 10 by repetitively applying i-edge-sums, for i ∈ {1, 2, 3}. We also use this result to give a structural characterization of graphs that exclude K3,3 as an immersion.",

keywords = "Branch-width, Graph immersions, Kuratowski graphs, Tree-width",

author = "Giannopoulou, {Archontia C.} and Marcin Kami{\'n}ski and Thilikos, {Dimitrios M.}",

note = "Publisher Copyright: {\textcopyright} 2014 Wiley Periodicals, Inc.",

year = "2015",

month = jan,

day = "1",

doi = "10.1002/jgt.21790",

language = "English (US)",

volume = "78",

pages = "43--60",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "1",

}

TY - JOUR

T1 - Forbidding Kuratowski graphs as immersions

AU - Giannopoulou, Archontia C.

AU - Kamiński, Marcin

AU - Thilikos, Dimitrios M.

PY - 2015/1/1

Y1 - 2015/1/1

N2 - Immersion is a containment relation on graphs that is weaker than topological minor. (Every topological minor of a graph is also its immersion.) The graphs that do not contain any of the Kuratowski graphs (K5 and K3,3) as topological minors are exactly planar graphs. We give a structural characterization of graphs that exclude the Kuratowski graphs as immersions. We prove that they can be constructed from planar graphs that are subcubic or of branch-width at most 10 by repetitively applying i-edge-sums, for i ∈ {1, 2, 3}. We also use this result to give a structural characterization of graphs that exclude K3,3 as an immersion.

AB - Immersion is a containment relation on graphs that is weaker than topological minor. (Every topological minor of a graph is also its immersion.) The graphs that do not contain any of the Kuratowski graphs (K5 and K3,3) as topological minors are exactly planar graphs. We give a structural characterization of graphs that exclude the Kuratowski graphs as immersions. We prove that they can be constructed from planar graphs that are subcubic or of branch-width at most 10 by repetitively applying i-edge-sums, for i ∈ {1, 2, 3}. We also use this result to give a structural characterization of graphs that exclude K3,3 as an immersion.

KW - Branch-width

KW - Graph immersions

KW - Kuratowski graphs

KW - Tree-width

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

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

U2 - 10.1002/jgt.21790

DO - 10.1002/jgt.21790

M3 - Article

AN - SCOPUS:84914174575

SN - 0364-9024

VL - 78

SP - 43

EP - 60

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 1

ER -

Forbidding Kuratowski graphs as immersions

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this