Approximating List-Coloring on a Fixed Surface

DOI10.1007/978-3-540-70575-8_28MaRDI QIDQ3521930zbMATH OpenOpenAlexFDO

Authors Ken-ichi Kawarabayashi

Publication date 28 August 2008

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-70575-8_28

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• List-coloring graphs on surfaces with varying list-sizes
• List-color-critical graphs on a fixed surface
• Near-optimal list colorings
• Complexity of list coloring problems with a fixed total number of colors
• On the number of list‐colorings
• A variation on Heawood list-coloring for graphs on surfaces
• Fixed-parameter tractability of (n-k) list coloring
• Fixed-parameter tractability of \((n-k)\) list coloring
• Publication:4934399
• On the complexity of a restricted list-coloring problem

Cited in

(5)

• A variation on Heawood list-coloring for graphs on surfaces
• Near-optimal list colorings
• List-color-critical graphs on a fixed surface
• Additive approximation algorithms for list-coloring minor-closed class of graphs
• List-coloring graphs without subdivisions and without immersions

This page was built for publication: Approximating List-Coloring on a Fixed Surface

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