An algorithm for coloring some perfect graphs

DOI10.1016/S0012-365X(97)00082-4MaRDI QIDQ1382811zbMATH OpenFDO

Authors Sylvain Gravier, Frédéric Maffray, Hacène Ait Haddadene

Publication date 14 September 1998

Published in Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

chromatic numbercolouringperfect graphscolouring algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Precoloring Extension III: Classes of Perfect Graphs
• Coloring perfect \((K_ 4\)-e)-free graphs
• A reduction procedure for coloring perfect \(K_ 4\)-free graphs
• On-line coloring of perfect graphs
• Perfect graphs
• scientific article; zbMATH DE number 108587
• scientific article; zbMATH DE number 4202279
• scientific article; zbMATH DE number 3869356
• Perfectly colorable graphs
• Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs

Cites work

• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 3168327 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• A reduction procedure for coloring perfect \(K_ 4\)-free graphs
• Coloring perfect \((K_ 4\)-e)-free graphs
• On rigid circuit graphs
• On weakly diamond-free Berge graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• The splittance of a graph

Cited in

(13)

• scientific article; zbMATH DE number 4144006 (Why is no real title available?)
• On word colourings and some perfect graphs
• An algorithm for colouring perfect planar graphs
• An exact method for graph coloring
• Coloring perfect \((K_ 4\)-e)-free graphs
• Perfect and locally perfect colorings
• Perfect colorings of the prism graph
• Exact Algorithms for Coloring Graphs While Avoiding Monochromatic Cycles
• On Tucker vertices of graphs
• A reduction procedure for coloring perfect \(K_ 4\)-free graphs
• Colouring Some Classes of Perfect Graphs Robustly
• scientific article; zbMATH DE number 1033812 (Why is no real title available?)
• scientific article; zbMATH DE number 108587 (Why is no real title available?)

This page was built for publication: An algorithm for coloring some perfect graphs

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