A linear 5-coloring algorithm of planar graphs
From MaRDI portal
Publication:3934416
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Related Items
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
