Excluding any graph as a minor allows a low tree-width 2-coloring

Matt DeVos; Guoli Ding; Bogdan Oporowski; Daniel P. Sanders; Bruce Reed; Paul Seymour; Dirk Vertigan

doi:10.1016/j.jctb.2003.09.001

Excluding any graph as a minor allows a low tree-width 2-coloring

Matt DeVos
, Guoli Ding
, Bogdan Oporowski
, Daniel P. Sanders
, Bruce Reed
, Paul Seymour
, Dirk Vertigan

Mathematics

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

86 Scopus citations

Abstract

This article proves the conjecture of Thomas that, for every graph G, there is an integer k such that every graph with no minor isomorphic to G has a 2-coloring of either its vertices or its edges where each color induces a graph of tree-width at most k. Some generalizations are also proved.

Original language	English (US)
Pages (from-to)	25-41
Number of pages	17
Journal	Journal of Combinatorial Theory. Series B
Volume	91
Issue number	1
DOIs	https://doi.org/10.1016/j.jctb.2003.09.001
State	Published - May 2004

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Edge partitions
Small components
Tree-width
Vertex partitions

Access to Document

10.1016/j.jctb.2003.09.001

Cite this

@article{a53b5edeaa304067b42d57048dbb297f,

title = "Excluding any graph as a minor allows a low tree-width 2-coloring",

abstract = "This article proves the conjecture of Thomas that, for every graph G, there is an integer k such that every graph with no minor isomorphic to G has a 2-coloring of either its vertices or its edges where each color induces a graph of tree-width at most k. Some generalizations are also proved.",

keywords = "Edge partitions, Small components, Tree-width, Vertex partitions",

author = "Matt DeVos and Guoli Ding and Bogdan Oporowski and Sanders, \{Daniel P.\} and Bruce Reed and Paul Seymour and Dirk Vertigan",

note = "Funding Information: E-mail addresses: [email protected] (M. DeVos), [email protected] (G. Ding), [email protected] (B. Oporowski), [email protected] (D.P. Sanders), [email protected] (B. Reed), [email protected] (P. Seymour), [email protected] (D. Vertigan). 1Partially supported by National Science Foundation under Grant DMS-9400946. 2Partially supported by the National Security Agency, Grant MDA904-94-H-2057. 3Partially supported by the Louisiana Education Quality Support Fund, Grant LEQSF(1995–98)–RD– A–08. 4Supported by the Office of Naval Research, Grant N00014-92-J-1965.",

year = "2004",

month = may,

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

language = "English (US)",

volume = "91",

pages = "25--41",

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

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Excluding any graph as a minor allows a low tree-width 2-coloring

AU - DeVos, Matt

AU - Ding, Guoli

AU - Oporowski, Bogdan

AU - Sanders, Daniel P.

AU - Reed, Bruce

AU - Seymour, Paul

AU - Vertigan, Dirk

N1 - Funding Information: E-mail addresses: [email protected] (M. DeVos), [email protected] (G. Ding), [email protected] (B. Oporowski), [email protected] (D.P. Sanders), [email protected] (B. Reed), [email protected] (P. Seymour), [email protected] (D. Vertigan). 1Partially supported by National Science Foundation under Grant DMS-9400946. 2Partially supported by the National Security Agency, Grant MDA904-94-H-2057. 3Partially supported by the Louisiana Education Quality Support Fund, Grant LEQSF(1995–98)–RD– A–08. 4Supported by the Office of Naval Research, Grant N00014-92-J-1965.

PY - 2004/5

Y1 - 2004/5

N2 - This article proves the conjecture of Thomas that, for every graph G, there is an integer k such that every graph with no minor isomorphic to G has a 2-coloring of either its vertices or its edges where each color induces a graph of tree-width at most k. Some generalizations are also proved.

AB - This article proves the conjecture of Thomas that, for every graph G, there is an integer k such that every graph with no minor isomorphic to G has a 2-coloring of either its vertices or its edges where each color induces a graph of tree-width at most k. Some generalizations are also proved.

KW - Edge partitions

KW - Small components

KW - Tree-width

KW - Vertex partitions

UR - https://www.scopus.com/pages/publications/2342457822

UR - https://www.scopus.com/pages/publications/2342457822#tab=citedBy

U2 - 10.1016/j.jctb.2003.09.001

DO - 10.1016/j.jctb.2003.09.001

M3 - Article

AN - SCOPUS:2342457822

SN - 0095-8956

VL - 91

SP - 25

EP - 41

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 1

ER -

Excluding any graph as a minor allows a low tree-width 2-coloring

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this