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

DOI10.1016/J.JCTB.2020.09.003MaRDI QIDQ2099409zbMATH OpenOpenAlexFDO

Authors 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

approximationcoloringminor-closed classes

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75)

Recommendations

• Additive non-approximability of chromatic number in proper minor-closed classes
• On the hardness of approximating the chromatic number
• Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs
• scientific article; zbMATH DE number 4108788
• On the additive chromatic number of several families of graphs
• A note on approximating the \(b\)-chromatic number
• Inapproximability of the lid-chromatic number
• Nordhaus-Gaddum inequalities for the fractional and circular chromatic numbers
• scientific article; zbMATH DE number 4008419
• On incompactness for chromatic number of graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1303525 (Why is no real title available?)
• scientific article; zbMATH DE number 7051287 (Why is no real title available?)
• A simple algorithm for 4-coloring 3-colorable planar graphs
• Additive non-approximability of chromatic number in proper minor-closed classes
• Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs
• Every planar graph is 5-choosable
• Excluding any graph as a minor allows a low tree-width 2-coloring
• Five-coloring maps on surfaces
• Graph minors. V. Excluding a planar graph
• Graph minors. XVI: Excluding a non-planar graph
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• Hadwiger's conjecture is decidable
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Lower bound of the Hadwiger number of graphs by their average degree

Cited in

(4)

• Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs
• Vertex-bipartition method for colouring minor-closed classes of graphs
• Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs
• Additive non-approximability of chromatic number in proper minor-closed classes

This page was built for publication: Additive non-approximability of chromatic number in proper minor-closed classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2099409)