@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: matdevos@math.princeton.edu (M. DeVos), ding@math.lsu.edu (G. Ding), bogdan@math.lsu.edu (B. Oporowski), sanders@graphtheory.com (D.P. Sanders), breed@cs.mcgill.ca (B. Reed), pds@math.princeton.edu (P. Seymour), vertigan@math.lsu.edu (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",

}