A fast algorithm for coloring Meyniel graphs

DOI10.1016/0095-8956(90)90078-EMaRDI QIDQ1111563zbMATH OpenOpenAlexDBLPWikidataFDO

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

algorithmgraph coloringmaximum cliqueMeyniel graphminimum coloringperfect graphs

Mathematics Subject Classification ID

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

Review text

We color the nodes of a graph by first applying successive contractions to non-adjacent nodes until we get a clique; then we color the clique and decontract the graph. We show that this algorithm provides a minimum coloring and a maximum clique for any Meyniel graph by using a simple rule for choosing which nodes are to be contracted. This \(O(n^ 3)\) algorithm is much simpler than those already existing for Meyniel graphs. Moreover, the optimality of this algorithm for Meyniel graphs provides an alternate nice proof of the following result of Hoàng: a graph G is Meyniel if and only if, for any induced subgraph of G, each node belongs to a stable set that meets all maximal cliques. Finally we give a new characterization for Meyniel graphs.

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

• A new property of critical imperfect graphs and some consequences
• A note on strong perfectness of graphs
• 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?)
• 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

(22)

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

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)