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 - http://www.scopus.com/inward/record.url?scp=2342457822&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=2342457822&partnerID=8YFLogxK
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 -