Additive non-approximability of chromatic number in proper minor-closed classes
From MaRDI portal
Publication:5002722
DOI10.4230/LIPIcs.ICALP.2018.47zbMath1499.68267arXiv1707.03888OpenAlexW2954260434MaRDI QIDQ5002722
Zdeněk Dvořák, Ken-ichi Kawarabayashi
Publication date: 28 July 2021
Full work available at URL: https://arxiv.org/abs/1707.03888
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph minors (05C83) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bound of the Hadwiger number of graphs by their average degree
- Graph minors. V. Excluding a planar graph
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- 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
This page was built for publication: Additive non-approximability of chromatic number in proper minor-closed classes
