Recognition of quasi-Meyniel graphs

DOI10.1016/S0166-218X(00)00290-0MaRDI QIDQ5951967zbMATH OpenFDO

Authors Celina M. H. de Figueiredo, Kristina Vušković

Publication date 2001

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0166-218X(00)00290-0

zbMATH Keywords

polynomial-time algorithmquasi-Meyniel graphs

Mathematics Subject Classification ID

Perfect graphs (05C17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 3889583
• scientific article; zbMATH DE number 3878985
• A Note on Quasi‐triangulated Graphs
• Holes and dominoes in Meyniel graphs
• Even and odd holes in cap-free graphs

Cites work

• A fast algorithm for coloring Meyniel graphs
• Even and odd holes in cap-free graphs
• Holes and dominoes in Meyniel graphs
• scientific article; zbMATH DE number 3889583 (Why is no real title available?)
• scientific article; zbMATH DE number 3168327 (Why is no real title available?)
• scientific article; zbMATH DE number 3904622 (Why is no real title available?)
• On the complexity of testing for odd holes and induced odd paths
• Short-chorded and perfect graphs
• Universally signable graphs

Cited in

(6)

• scientific article; zbMATH DE number 3878985 (Why is no real title available?)
• Coloring vertices of a graph or finding a Meyniel obstruction
• A Note on Quasi‐triangulated Graphs
• Recognition of Graphs with Convex Quadratic Stability Number
• Recognizing planar strict quasi-parity graphs
• On some classes of quasi-triangulated graphs

This page was built for publication: Recognition of quasi-Meyniel graphs

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