Additive non-approximability of chromatic number in proper minor-closed classes
From MaRDI portal
Publication:2099409
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
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