A fast algorithm for coloring Meyniel graphs
From MaRDI portal
Publication:1111563
DOI10.1016/0095-8956(90)90078-EzbMath0658.05027OpenAlexW2013879243WikidataQ56430115 ScholiaQ56430115MaRDI QIDQ1111563
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
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (18)
Path parity and perfection ⋮ Coloring the cliques of line graphs ⋮ Lagrangean relaxation with clusters and column generation for the manufacturer's pallet loading problem ⋮ Structure and algorithms for (cap, even hole)-free graphs ⋮ Perfectly contractile graphs and quadratic toric rings ⋮ Coloring vertices of a graph or finding a Meyniel obstruction ⋮ On domination elimination orderings and domination graphs ⋮ Classes of perfect graphs ⋮ COSINE: A new graph coloring algorithm ⋮ A new characterization of HH-free graphs ⋮ Counterexamples to three conjectures concerning perfect graphs ⋮ Recognition of quasi-Meyniel graphs ⋮ HOLES AND DOMINOES IN MEYNIEL GRAPHS ⋮ The variational quantum eigensolver: a review of methods and best practices ⋮ A class of perfectly contractile graphs ⋮ Perfectly contractile graphs ⋮ Coloring Meyniel graphs in linear time ⋮ Colouring Some Classes of Perfect Graphs Robustly
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Perfectly contractile graphs
- Perfectly orderable graphs are quasi-parity graphs: a short proof
- On a conjecture of Meyniel
- A new property of critical imperfect graphs and some consequences
- The ellipsoid method and its consequences in combinatorial optimization
- Meyniel graphs are strongly perfect
- On the perfect graph conjecture
- A note on strong perfectness of graphs
This page was built for publication: A fast algorithm for coloring Meyniel graphs
