A fast algorithm for coloring Meyniel graphs

DOI10.1016/0095-8956(90)90078-EzbMATH Open0658.05027DBLPjournals/jct/Hertz90OpenAlexW2013879243WikidataQ56430115 ScholiaQ56430115MaRDI QIDQ1111563FDOQ1111563

Authors Alain Hertz

Publication date 1990

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0095-8956(90)90078-e

zbMATH Keywords

algorithmmaximum cliquegraph coloringperfect graphsminimum coloringMeyniel graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Recommendations

• An \(O(n^2)\) algorithm to color Meyniel graphs
• scientific article; zbMATH DE number 1043838
• Coloring Meyniel graphs in linear time
• Holes and dominoes in Meyniel graphs
• On a conjecture of Meyniel

Cites work

• scientific article; zbMATH DE number 3889564 (Why is no real title available?)
• scientific article; zbMATH DE number 3889565 (Why is no real title available?)
• scientific article; zbMATH DE number 3904622 (Why is no real title available?)
• scientific article; zbMATH DE number 3908479 (Why is no real title available?)
• scientific article; zbMATH DE number 3338381 (Why is no real title available?)
• A new property of critical imperfect graphs and some consequences
• A note on strong perfectness of graphs
• Meyniel graphs are strongly perfect
• On a conjecture of Meyniel
• On the perfect graph conjecture
• Perfectly contractile graphs
• Perfectly orderable graphs are quasi-parity graphs: a short proof
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(21)

• The variational quantum eigensolver: a review of methods and best practices
• Lagrangean relaxation with clusters and column generation for the manufacturer's pallet loading problem
• Incidence coloring of mycielskians with fast algorithm
• Perfectly contractile graphs
• Recognition of quasi-Meyniel graphs
• Coloring vertices of a graph or finding a Meyniel obstruction
• Coloring the cliques of line graphs
• A new characterization of HH-free graphs
• Counterexamples to three conjectures concerning perfect graphs
• Structure and algorithms for (cap, even hole)-free graphs
• COSINE: A new graph coloring algorithm
• On domination elimination orderings and domination graphs
• Colouring Some Classes of Perfect Graphs Robustly
• Coloring Meyniel graphs in linear time
• Holes and dominoes in Meyniel graphs
• A class of perfectly contractile graphs
• Perfectly contractile graphs and quadratic toric rings
• An \(O(n^2)\) algorithm to color Meyniel graphs
• Classes of perfect graphs
• On a conjecture of Meyniel
• Path parity and perfection

This page was built for publication: A fast algorithm for coloring Meyniel graphs

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