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-widlh at most k. Some generalizations are also proved. |
Year | DOI | Venue |
---|---|---|
2004 | 10.1016/j.jctb.2003.09.001 | J. Comb. Theory, Ser. B |
Keywords | DocType | Volume |
vertex partitions,low tree-width 2-coloring,edge partitions,. tree-width,small components,tree-width,minor isomorphic,graph g,secondary 05c55,primary 05c15,integer k,small components. 1this author's research was partially supported by national science foundation under grant,edge coloring,tree width | Journal | 91 |
Issue | ISSN | Citations |
1 | Journal of Combinatorial Theory, Series B | 53 |
PageRank | References | Authors |
2.67 | 12 | 7 |
Name | Order | Citations | PageRank |
---|---|---|---|
Matt DeVos | 1 | 172 | 25.17 |
Guoli Ding | 2 | 444 | 51.58 |
Bogdan Oporowski | 3 | 266 | 23.24 |
Daniel P. Sanders | 4 | 471 | 45.56 |
Bruce Reed | 5 | 305 | 16.94 |
Paul Seymour | 6 | 1262 | 92.96 |
Dirk Vertigan | 7 | 331 | 32.14 |