On decidability of hyperbolicity

DOI10.1007/S00493-022-4891-8MaRDI QIDQ6969987zbMATH OpenFDO

Authors Zdeněk Dvořák, Luke Postle

Publication date 19 June 2025

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00493-022-4891-8

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)

Cites work

• 3-list-coloring graphs of girth at least five on surfaces
• 3-list-coloring planar graphs of girth 5
• 5-list-coloring planar graphs with distant precolored vertices
• A Separator Theorem for Planar Graphs
• Every planar graph is 5-choosable
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Exponentially many 5-list-colorings of planar graphs
• Five-list-coloring graphs on surfaces. II: A linear bound for critical graphs in a disk.
• Graphs with two crossings are 5-choosable
• Hyperbolic families and coloring graphs on surfaces
• Linear-time and efficient distributed algorithms for list coloring graphs on surfaces
• List-coloring embedded graphs
• On acyclic colorings of planar graphs
• The Alon-Tarsi number of planar graphs
• The four-colour theorem
• Three-coloring triangle-free graphs on surfaces. III. Graphs of girth five

Cited in

(1)

• 5-list coloring toroidal 6-regular triangulations in linear time

This page was built for publication: On decidability of hyperbolicity

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