Coloring planar perfect graphs by decomposition

DOI10.1007/BF02579263MaRDI QIDQ1093649zbMATH OpenOpenAlexFDO

Authors B. George

Publication date 1986

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02579263

zbMATH Keywords

colouring algorithmcolouring perfect graphsdecomposition schemeperfect planar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Review text

This paper describes a decomposition scheme for colouring perfect graphs, so that it suffices to colour perfect graphs which are well connected. This approach yields a new good colouring algorithm for perfect planar graphs, and it seems that the approach goes further.

Recommendations

• Complete colorings of planar graphs
• Coloring perfect degenerate graphs
• scientific article; zbMATH DE number 4049083
• An algorithm for colouring perfect planar graphs
• Colouring planar graphs
• Two-colourings that decompose perfect graphs
• scientific article; zbMATH DE number 1944138
• Coloring decompositions of complete geometric graphs
• On the total coloring of planar graphs.
• scientific article; zbMATH DE number 1347005

Cites work

• An O(N2) algorithm for coloring perfect planar graphs
• scientific article; zbMATH DE number 3394154 (Why is no real title available?)
• The ellipsoid method and its consequences in combinatorial optimization
• The Strong Perfect Graph Conjecture for Planar Graphs

Cited in

(9)

• Decomposition of perfect graphs
• Coloring perfect degenerate graphs
• On planar perfectly contractile graphs
• An algorithm for colouring perfect planar graphs
• An O(N2) algorithm for coloring perfect planar graphs
• scientific article; zbMATH DE number 4049083 (Why is no real title available?)
• scientific article; zbMATH DE number 1033812 (Why is no real title available?)
• Colouring perfect planar graphs in parallel
• Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs

This page was built for publication: Coloring planar perfect graphs by decomposition

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