A linear 5-coloring algorithm of planar graphs

DOI10.1016/0196-6774(81)90031-6zbMath0478.05041OpenAlexW2030781850MaRDI QIDQ3934416

Nobuji Saito, Norishige Chiba, Takao Nishizeki

Publication date: 1981

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(81)90031-6

zbMATH Keywords

computational complexitygraph coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items (12)

The \(d\)-precoloring problem for \(k\)-degenerate graphs ⋮ An efficient parallel algorithm for finding rectangular duals of plane triangular graphs ⋮ Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs ⋮ Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs ⋮ Fast 3-coloring triangle-free planar graphs ⋮ Coloring certain proximity graphs ⋮ Heuristic for rapidly four-coloring large planar graphs ⋮ Non-monochromatic and conflict-free colorings on tree spaces and planar network spaces ⋮ Storing the subdivision of a polyhedral surface ⋮ Improved Induced Matchings in Sparse Graphs ⋮ On linear-time algorithms for five-coloring planar graphs ⋮ An efficient parallel algorithm for computing a large independent set in a planar graph

This page was built for publication: A linear 5-coloring algorithm of planar graphs