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

DOI10.1016/j.jctb.2003.09.001zbMath1042.05036OpenAlexW2037789845MaRDI QIDQ1826951

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

Publication date: 6 August 2004

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2003.09.001

zbMATH Keywords

Tree-widthVertex partitionsEdge partitionsSmall components

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph minors (05C83) Generalized Ramsey theory (05C55)

Related Items

On Universal Graphs of Minor Closed Families, Some recent progress and applications in graph minor theory, The \(k\)-strong induced arboricity of a graph, A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three, PTAS for Sparse General-valued CSPs, A \(p\)-centered coloring for the grid using \(O(p)\) colors, On weighted sublinear separators, On graph thickness, geometric thickness, and separator theorems, Sublinear separators, fragility and subexponential expansion, On low tree-depth decompositions, Grad and classes with bounded expansion. I: Decompositions, Grad and classes with bounded expansion. II: Algorithmic aspects, Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities, Partitioning into graphs with only small components, Approximation algorithms via contraction decomposition, On fractional fragility rates of graph classes, Characterisations and examples of graph classes with bounded expansion, On generalized choice and coloring numbers, Orthogonal Tree Decompositions of Graphs, Polynomial bounds for centered colorings on proper minor-closed graph classes, Partitioning \(H\)-minor free graphs into three subgraphs with no large components, Additive non-approximability of chromatic number in proper minor-closed classes, Tree-depth, subgraph coloring and homomorphism bounds, Vertex-Bipartition Method for Colouring Minor-Closed Classes of Graphs, Game coloring the Cartesian product of graphs, On low rank-width colorings, Bounds on vertex colorings with restrictions on the union of color classes, Colouring games on outerplanar graphs and trees, Hadwiger’s Conjecture, Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness, Colouring graphs with bounded generalized colouring number, Counting Homomorphisms to Sparse Graphs, Surfaces, tree-width, clique-minors, and partitions, Additive non-approximability of chromatic number in proper minor-closed classes, Unnamed Item, The Grad of a Graph and Classes with Bounded Expansion, Fraternal Augmentations of graphs, Coloration and Minors

Cites Work

• Graph minors. XX: Wagner's conjecture
• Graph minors. III. Planar tree-width
• Graph minors. V. Excluding a planar graph
• Partitioning graphs of bounded tree-width
• Quickly excluding a planar graph
• Graph minors. XVI: Excluding a non-planar graph
• Surfaces, tree-width, clique-minors, and partitions
• Graphs with forbidden subgraphs