A linear 5-coloring algorithm of planar graphs
From MaRDI portal
Publication:3934416
DOI10.1016/0196-6774(81)90031-6zbMath0478.05041MaRDI QIDQ3934416
Norishige Chiba, Takao Nishizeki, Nobuji Saito
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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C15: Coloring of graphs and hypergraphs
Related Items
An efficient parallel algorithm for computing a large independent set in a planar graph, Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs, Coloring certain proximity graphs, On linear-time algorithms for five-coloring planar graphs, Heuristic for rapidly four-coloring large planar graphs, Storing the subdivision of a polyhedral surface, An efficient parallel algorithm for finding rectangular duals of plane triangular graphs, Fast 3-coloring triangle-free planar graphs, The \(d\)-precoloring problem for \(k\)-degenerate graphs, Improved Induced Matchings in Sparse Graphs