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

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

zbMATH Keywords

approximation; coloring; minor-closed classes

Mathematics Subject Classification ID

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