Excluding any graph as a minor allows a low tree-width 2-coloring

Matt DeVos, Guoli Ding, Bogdan Oporowski, Daniel P. Sanders, Bruce Reed, Paul Seymour, Dirk Vertigan

Research output: Contribution to journalArticlepeer-review

80 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)25-41
Number of pages17
JournalJournal of Combinatorial Theory. Series B
Volume91
Issue number1
DOIs
StatePublished - May 2004

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Edge partitions
  • Small components
  • Tree-width
  • Vertex partitions

Fingerprint

Dive into the research topics of 'Excluding any graph as a minor allows a low tree-width 2-coloring'. Together they form a unique fingerprint.

Cite this