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