Graph minors. III. Planar tree-width

Neil Robertson; P. D. Seymour

doi:10.1016/0095-8956(84)90013-3

Graph minors. III. Planar tree-width

Neil Robertson, P. D. Seymour

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

552 Scopus citations

Abstract

The "tree-width" of a graph is defined and it is proved that for any fixed planar graph H, every planar graph with sufficiently large tree-width has a minor isomorphic to H. This result has several applications which are described in other papers in this series.

Original language	English (US)
Pages (from-to)	49-64
Number of pages	16
Journal	Journal of Combinatorial Theory, Series B
Volume	36
Issue number	1
DOIs	https://doi.org/10.1016/0095-8956(84)90013-3
State	Published - Feb 1984
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/0095-8956(84)90013-3

Cite this

@article{b045acd76fb041aaab0e2d4aa083626e,

title = "Graph minors. III. Planar tree-width",

abstract = "The {"}tree-width{"} of a graph is defined and it is proved that for any fixed planar graph H, every planar graph with sufficiently large tree-width has a minor isomorphic to H. This result has several applications which are described in other papers in this series.",

author = "Neil Robertson and Seymour, {P. D.}",

note = "Funding Information: Thus, for example, trees and forests have tree-width 1 (or 0 in degenerate * Research partially supported by NSF Grant MCS 8103440. 49",

year = "1984",

month = feb,

doi = "10.1016/0095-8956(84)90013-3",

language = "English (US)",

volume = "36",

pages = "49--64",

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

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Graph minors. III. Planar tree-width

AU - Robertson, Neil

AU - Seymour, P. D.

N1 - Funding Information: Thus, for example, trees and forests have tree-width 1 (or 0 in degenerate * Research partially supported by NSF Grant MCS 8103440. 49

PY - 1984/2

Y1 - 1984/2

N2 - The "tree-width" of a graph is defined and it is proved that for any fixed planar graph H, every planar graph with sufficiently large tree-width has a minor isomorphic to H. This result has several applications which are described in other papers in this series.

AB - The "tree-width" of a graph is defined and it is proved that for any fixed planar graph H, every planar graph with sufficiently large tree-width has a minor isomorphic to H. This result has several applications which are described in other papers in this series.

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

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

U2 - 10.1016/0095-8956(84)90013-3

DO - 10.1016/0095-8956(84)90013-3

M3 - Article

AN - SCOPUS:48749140617

SN - 0095-8956

VL - 36

SP - 49

EP - 64

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 1

ER -

Graph minors. III. Planar tree-width

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this