scientific article; zbMATH DE number 3889583

From MaRDI portal
Publication:3222886





[For the entire collection see Zbl 0546.00006.] A graph in which every odd elementary cycle of length at least 5 has at least two chords is called a Meyniel graph. Every Meyniel graph is perfect. A polynomial-time recognition algorithm for Meyniel graphs is presented. The algorithm is based on a new decomposition property of Meyniel graphs. As a by-product, some new results on triangulated, o- triangulated and parity graphs, which all are Meyniel graphs, are also obtained.











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 Q3222886)