Vertex-Bipartition Method for Colouring Minor-Closed Classes of Graphs

DOI10.1017/S0963548310000076zbMath1198.05140OpenAlexW2091606970MaRDI QIDQ4933601

Guoli Ding, Stan Dziobiak

Publication date: 14 October 2010

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548310000076

zbMATH Keywords

colouring algorithmclique sum operationdegenerate valueminor closed class of graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Hadwiger’s Conjecture

Cites Work

• Graph minors. V. Excluding a planar graph
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Quickly excluding a planar graph
• A simpler proof of the excluded minor theorem for higher surfaces
• Graph minors. XVI: Excluding a non-planar graph
• Diameter and treewidth in minor-closed graph families, revisited
• Excluding any graph as a minor allows a low tree-width 2-coloring
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Graph minors. II. Algorithmic aspects of tree-width
• Combinatorial Local Planarity and the Width of Graph Embeddings
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth