An O(N2) algorithm for coloring perfect planar graphs

DOI10.1016/0196-6774(84)90040-3zbMATH Open0538.05036OpenAlexW2058660326MaRDI QIDQ3323978FDOQ3323978

Authors Donna M. Wilson, Alan C. Tucker

Publication date 1984

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

Full work available at URL https://doi.org/10.1016/0196-6774(84)90040-3

zbMATH Keywords

chromatic numberperfect planar graphsmaximal clique size

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)

Recommendations

• scientific article; zbMATH DE number 4049083
• An algorithm for colouring perfect planar graphs
• Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs
• Coloring planar perfect graphs by decomposition
• scientific article; zbMATH DE number 1256776

Cited in

(7)

• An algorithm for colouring perfect planar graphs
• scientific article; zbMATH DE number 4049083 (Why is no real title available?)
• Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs
• scientific article; zbMATH DE number 1982173 (Why is no real title available?)
• Perfect and locally perfect colorings
• Coloring planar perfect graphs by decomposition
• Colouring perfect planar graphs in parallel

This page was built for publication: An O(N2) algorithm for coloring perfect planar graphs

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