A linear 5-coloring algorithm of planar graphs

DOI10.1016/0196-6774(81)90031-6MaRDI QIDQ3934416zbMATH OpenOpenAlexFDO

Authors Norishige Chiba, Nobuji Saito, 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

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

Cited in

(14)

• 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
• Non-monochromatic and conflict-free colorings on tree spaces and planar network spaces
• The d-precoloring problem for k-degenerate graphs
• Improved induced matchings in sparse graphs
• Physical zero-knowledge proofs for Five Cells
• 5-coloring planar graphs with a color class of order at most \(|V|/6\)
• An efficient parallel algorithm for computing a large independent set in a planar graph
• Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs
• Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs
• Coloring certain proximity graphs

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

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