×

zbMATH — the first resource for mathematics

Excluding any graph as a minor allows a low tree-width 2-coloring. (English) Zbl 1042.05036
Summary: 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.

MSC:
05C15 Coloring of graphs and hypergraphs
05C55 Generalized Ramsey theory
05C83 Graph minors
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Chartrand, G.; Geller, D.; Hedetniemi, S., Graphs with forbidden subgraphs, J. combin. theory ser. B, 10, 12-41, (1971) · Zbl 0223.05101
[2] Ding, G.; Oporowski, B.; Sanders, D.P.; Vertigan, D., Partitioning graphs of bounded tree-width, Combinatorica, 18, 1, 1-12, (1998) · Zbl 0924.05022
[3] Ding, G.; Oporowski, B.; Sanders, D.P.; Vertigan, D., Surfaces, tree-width, clique-minors, and partitions, J. combin. theory ser. B, 79, 221-246, (2000) · Zbl 1029.05041
[4] N. Robertson, P.D. Seymour, private communication.
[5] Robertson, N.; Seymour, P.D., Graph minors. III. planar tree-width, J. combin. theory ser. B, 36, 49-64, (1984) · Zbl 0548.05025
[6] Robertson, N.; Seymour, P.D., Graph minors. V. excluding a planar graph, J. combin. theory ser. B, 41, 92-114, (1986) · Zbl 0598.05055
[7] Robertson, N.; Seymour, P.D., Graph minors. XVI. excluding a non-planar graph, J. combin. theory ser. B, 89, 43-76, (2003) · Zbl 1023.05040
[8] N. Robertson, P.D. Seymour, Graph Minors. XX. Wagner’s conjecture, (1988), submitted for publication. · Zbl 1061.05088
[9] Robertson, N.; Seymour, P.D.; Thomas, R., Quickly excluding a planar graph, J. combin. theory ser. B, 62, 323-348, (1994) · Zbl 0807.05023
[10] Thomas, R., Problem session of the third slovene conference on graph theory, (1995), Bled Slovenia
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.