A characterization of some graph classes using excluded minors

Janka Chlebikova

doi:10.1007/s10998-007-3001-4

A characterization of some graph classes using excluded minors

Janka Chlebikova

School of Computing

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

224 Downloads (Pure)

Abstract

In this article we present a structural characterization of graphs
without K_5 and the octahedron as a minor. We introduce semiplanar
graphs as arbitrary sums of planar graphs, and give their characteriza-
tion in terms of excluded minors. Some other excluded minor theorems
for 3-connected minors are shown.

Original language	English
Pages (from-to)	1-9
Journal	Periodica Mathematica Hungarica
Volume	55
Issue number	1
DOIs	https://doi.org/10.1007/s10998-007-3001-4
Publication status	Published - 2007

Keywords

excluded minors
tree-width of a graph
=<k-sum of graphs

Access to Document

10.1007/s10998-007-3001-4

excludAccepted author manuscript (Post-print), 133 KBLicence: CC BY

Cite this

@article{2d0aa654aec2423e9e23c6c40427e653,

title = "A characterization of some graph classes using excluded minors",

abstract = "In this article we present a structural characterization of graphs without K\_5 and the octahedron as a minor. We introduce semiplanar graphs as arbitrary sums of planar graphs, and give their characteriza- tion in terms of excluded minors. Some other excluded minor theorems for 3-connected minors are shown.",

keywords = "excluded minors, tree-width of a graph, =<k-sum of graphs",

author = "Janka Chlebikova",

year = "2007",

doi = "10.1007/s10998-007-3001-4",

language = "English",

volume = "55",

pages = "1--9",

journal = "Periodica Mathematica Hungarica",

issn = "0031-5303",

publisher = "Springer Nature",

number = "1",

}

TY - JOUR

T1 - A characterization of some graph classes using excluded minors

AU - Chlebikova, Janka

PY - 2007

Y1 - 2007

N2 - In this article we present a structural characterization of graphs without K_5 and the octahedron as a minor. We introduce semiplanar graphs as arbitrary sums of planar graphs, and give their characteriza- tion in terms of excluded minors. Some other excluded minor theorems for 3-connected minors are shown.

AB - In this article we present a structural characterization of graphs without K_5 and the octahedron as a minor. We introduce semiplanar graphs as arbitrary sums of planar graphs, and give their characteriza- tion in terms of excluded minors. Some other excluded minor theorems for 3-connected minors are shown.

KW - excluded minors

KW - tree-width of a graph

KW - =<k-sum of graphs

U2 - 10.1007/s10998-007-3001-4

DO - 10.1007/s10998-007-3001-4

M3 - Article

SN - 0031-5303

VL - 55

SP - 1

EP - 9

JO - Periodica Mathematica Hungarica

JF - Periodica Mathematica Hungarica

IS - 1

ER -

A characterization of some graph classes using excluded minors

Abstract

Keywords

Access to Document

Fingerprint

Cite this