Additive approximation algorithms for list-coloring minor-closed class of graphs

MaRDI QIDQ4633931zbMATH OpenFDO

Authors Ken-ichi Kawarabayashi, Erik D. Demaine, Mohammad T. Hajiaghayi

Publication date 6 May 2019

Full work available at URL https://dl.acm.org/citation.cfm?id=1496896

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• 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
• Additive non-approximability of chromatic number in proper minor-closed classes
• Approximating List-Coloring on a Fixed Surface
• List-coloring graphs without subdivisions and without immersions

Cited in

(5)

• 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
• Additive non-approximability of chromatic number in proper minor-closed classes
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• List-coloring graphs without subdivisions and without immersions

This page was built for publication: Additive approximation algorithms for list-coloring minor-closed class of graphs

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