Additive non-approximability of chromatic number in proper minor-closed classes

DOI10.1016/j.jctb.2020.09.003zbMath1503.05102OpenAlexW3088731923MaRDI QIDQ2099409

Zdeněk Dvořák, Ken-ichi Kawarabayashi

Publication date: 23 November 2022

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.2020.09.003

zbMATH Keywords

approximationcoloringminor-closed classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bound of the Hadwiger number of graphs by their average degree
• A simple algorithm for 4-coloring 3-colorable planar graphs
• Graph minors. V. Excluding a planar graph
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• Five-coloring maps on surfaces
• Every planar graph is 5-choosable
• Graph minors. XVI: Excluding a non-planar graph
• Excluding any graph as a minor allows a low tree-width 2-coloring
• Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs
• Additive non-approximability of chromatic number in proper minor-closed classes
• Hadwiger's conjecture is decidable