An algorithm for colouring perfect planar graphs

DOI10.1016/0020-0190(89)90075-6zbMath0684.05019OpenAlexW2043646993MaRDI QIDQ1825203

Iain A. Stewart

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90075-6

zbMATH Keywords

planar graphsperfect graphperfect planar graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Related Items (1)

Classes of perfect graphs

Cites Work

• Unnamed Item
• The strong perfect graph conjecture for toroidal graphs
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
• Some simplified NP-complete graph problems
• Critical perfect graphs and perfect 3-chromatic graphs
• An O(N2) algorithm for coloring perfect planar graphs
• A Separator Theorem for Planar Graphs
• On the Problem of Partitioning Planar Graphs
• The Strong Perfect Graph Conjecture for Planar Graphs
• Perfect Graphs and an Application to Optimizing Municipal Services

This page was built for publication: An algorithm for colouring perfect planar graphs