@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",
}