Additive non-approximability of chromatic number in proper minor-closed classes
From MaRDI portal
Publication:2099409
DOI10.1016/j.jctb.2020.09.003zbMath1503.05102MaRDI 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
68Q25: Analysis of algorithms and problem complexity
05C75: Structural characterization of families of graphs
05C15: Coloring of graphs and hypergraphs
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms