scientific article; zbMATH DE number 3878985
From MaRDI portal
Publication:3344031
[For the entire collection see Zbl 0535.00030.] The Meyniel graphs are perfect graphs in which every odd elementary cycle of length at least five contains at least two chords. The paper shows that the recognition problem of a Meyniel graph is polynomial by presenting a polynomial recognition algorithm. As a by-product the authors obtain new results concerning some classes contained in Meyniel graphs: triangulated graphs, o-triangulated graphs and parity graphs.
Recommendations
Cited in
(23)- On a conjecture of Meyniel
- Quasi-star-cutsets and some consequences
- Structure and algorithms for (cap, even hole)-free graphs
- Graphs vertex-partitionable into strong cliques
- Decomposition techniques applied to the clique-stable set separation problem
- An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs
- On the linear extension complexity of stable set polytopes for perfect graphs
- Detecting strong cliques
- 2-clique-bond of stable set polyhedra
- Even-hole-free graphs. I: Decomposition theorem
- Recognizing \(i\)-triangulated graphs in \(O(mn)\) time
- Amalgams and -boundedness
- Graphs of separability at most two: structural characterizations and their consequences
- scientific article; zbMATH DE number 3889583 (Why is no real title available?)
- Coloring Meyniel graphs in linear time
- Colouring Some Classes of Perfect Graphs Robustly
- Substitution and \(\chi\)-boundedness
- A mickey-mouse decomposition theorem
- Holes and dominoes in Meyniel graphs
- Strong cliques in diamond-free graphs
- An O(n^2) algorithm to color Meyniel graphs
- Recognition of quasi-Meyniel graphs
- Stable sets and graphs with no even holes
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3344031)