On linear-time algorithms for five-coloring planar graphs

DOI10.1016/0020-0190(84)90056-5zbMath0563.05023OpenAlexW2028550759MaRDI QIDQ1057278

Greg N. Frederickson

Publication date: 1984

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(84)90056-5

zbMATH Keywords

planar graphlinear time algorithms5-coloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Related Items (7)

The \(d\)-precoloring problem for \(k\)-degenerate graphs ⋮ Branch-and-bound techniques for the maximum planar subgraph problem^∗ ⋮ Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs ⋮ Coloring certain proximity graphs ⋮ Heuristic for rapidly four-coloring large planar graphs ⋮ Contracting a Planar Graph Efficiently ⋮ An efficient parallel algorithm for computing a large independent set in a planar graph

Cites Work

• Every planar map is four colorable. I: Discharging
• A batching method for coloring planar graphs
• A linear 5-coloring algorithm of planar graphs
• Unnamed Item

This page was built for publication: On linear-time algorithms for five-coloring planar graphs