Additive non-approximability of chromatic number in proper minor-closed classes
DOI10.1016/J.JCTB.2020.09.003zbMATH Open1503.05102OpenAlexW3088731923MaRDI QIDQ2099409FDOQ2099409
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
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
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)
Cites Work
- Title not available (Why is that?)
- Linear degree extractors and the inapproximability of max clique and chromatic number
- 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
- Hadwiger's conjecture for \(K_ 6\)-free graphs
- Five-coloring maps on surfaces
- Every planar graph is 5-choosable
- Title not available (Why is that?)
- Graph minors. XVI: Excluding a non-planar graph
- Excluding any graph as a minor allows a low tree-width 2-coloring
- Hadwiger's conjecture is decidable
- A simple algorithm for 4-coloring 3-colorable planar graphs
- Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs
- Title not available (Why is that?)
- Additive non-approximability of chromatic number in proper minor-closed classes
Cited In (4)
- Additive non-approximability of chromatic number in proper minor-closed classes
- Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs
- Vertex-bipartition method for colouring minor-closed classes of graphs
- 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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2099409)
