Editing Meyniel graph (section)

{{short description|Graph where all odd cycles of length ≥ 5 has 2+ chords}}
[[File:Chordal-graph.svg|thumb|In a Meyniel graph, every long odd cycle (such as the black 5-cycle shown here) must have at least two chords (green)]]

In [[graph theory]], a '''Meyniel graph''' is a [[Graph (discrete mathematics)|graph]] in which every odd [[Cycle (graph theory)|cycle]] of length five or more has at least two [[Chordal graph|chords]] (edges connecting non-consecutive [[Vertex (graph theory)|vertices]] of the cycle).<ref name="isgci"/> The chords may be uncrossed (as shown in the figure) or they may cross each other, as long as there are at least two of them.

The Meyniel graphs are named after Henri Meyniel (also known for [[Cop number|Meyniel's conjecture]]), who proved that they are [[perfect graph]]s in 1976,<ref name="m76">{{citation
 | last = Meyniel | first = H.
 | doi = 10.1016/S0012-365X(76)80008-8
 | issue = 4
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 0439682
 | pages = 339–342
 | title = On the perfect graph conjecture
 | volume = 16
 | year = 1976| doi-access = free
 }}.</ref> long before the proof of the [[strong perfect graph theorem]] completely characterized the perfect graphs.
The same result was independently discovered by {{harvtxt|Markosjan|Karapetjan|1976}}.<ref name="mk">{{citation
 | last1 = Markosjan | first1 = S. E.
 | last2 = Karapetjan | first2 = I. A.
 | issue = 5
 | journal = Doklady Akademiya Nauk Armyanskoĭ SSR
 | mr = 0450130
 | pages = 292–296
 | title = Perfect graphs
 | volume = 63
 | year = 1976}}.</ref>