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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Cites Work
- The ellipsoid method and its consequences in combinatorial optimization
- Title not available (Why is that?)
- Title not available (Why is that?)
- Perfectly contractile graphs
- Title not available (Why is that?)
- On a conjecture of Meyniel
- On the perfect graph conjecture
- Title not available (Why is that?)
- A new property of critical imperfect graphs and some consequences
- Perfectly orderable graphs are quasi-parity graphs: a short proof
- Meyniel graphs are strongly perfect
- Title not available (Why is that?)
- A note on strong perfectness of graphs
Cited In (21)
- Coloring Meyniel graphs in linear time
- A class of perfectly contractile graphs
- Counterexamples to three conjectures concerning perfect graphs
- On domination elimination orderings and domination graphs
- Colouring Some Classes of Perfect Graphs Robustly
- Path parity and perfection
- Recognition of quasi-Meyniel graphs
- HOLES AND DOMINOES IN MEYNIEL GRAPHS
- Coloring vertices of a graph or finding a Meyniel obstruction
- Coloring the cliques of line graphs
- Structure and algorithms for (cap, even hole)-free graphs
- An \(O(n^2)\) algorithm to color Meyniel graphs
- On a conjecture of Meyniel
- Lagrangean relaxation with clusters and column generation for the manufacturer's pallet loading problem
- Incidence coloring of mycielskians with fast algorithm
- Classes of perfect graphs
- Perfectly contractile graphs
- COSINE: A new graph coloring algorithm
- Perfectly contractile graphs and quadratic toric rings
- A new characterization of HH-free graphs
- The variational quantum eigensolver: a review of methods and best practices
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)
