Additive non-approximability of chromatic number in proper minor-closed classes
type: Item
instance of: scholarly article
title: Additive non-approximability of chromatic number in proper minor-closed classes
zbMATH Open document ID: 1503.05102
author: Zdeněk Dvořák
author: Ken-ichi Kawarabayashi
published in: Journal of Combinatorial Theory. Series B
publication date: 2022-11-23T00:00:00Z
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 7622599
zbMATH Keywords: minor-closed classes
zbMATH Keywords: coloring
zbMATH Keywords: approximation
MaRDI profile type: Publication
full work available at URL: j.jctb.2020.09.003
OpenAlex ID: W3088731923
cites work: Linear time algorithms for NP-hard problems restricted to partial k- trees
cites work: Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs
cites work: Excluding any graph as a minor allows a low tree-width 2-coloring
cites work: Additive non-approximability of chromatic number in proper minor-closed classes
cites work: Q4198056
cites work: A simple algorithm for 4-coloring 3-colorable planar graphs
cites work: Hadwiger's conjecture is decidable
cites work: Q4633931
cites work: Lower bound of the Hadwiger number of graphs by their average degree
cites work: Q4250147
cites work: Graph minors. V. Excluding a planar graph
cites work: Graph minors. XVI: Excluding a non-planar graph
cites work: Hadwiger's conjecture for \(K_ 6\)-free graphs
cites work: Five-coloring maps on surfaces
cites work: Every planar graph is 5-choosable
cites work: Q3002782
DOI: 10.1016/J.JCTB.2020.09.003
Recommended article: Additive non-approximability of chromatic number in proper minor-closed classes
Recommended article: On the hardness of approximating the chromatic number
Recommended article: Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs
Recommended article: Q3832589
Recommended article: On the additive chromatic number of several families of graphs
Recommended article: A note on approximating the \(b\)-chromatic number
Recommended article: Inapproximability of the lid-chromatic number
Recommended article: Nordhaus-Gaddum inequalities for the fractional and circular chromatic numbers
Recommended article: Q3758854
Recommended article: On incompactness for chromatic number of graphs
description: scientific article; zbMATH DE number 7622599