Editing Meyniel graph

{{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>

==Perfection==
The Meyniel graphs are a subclass of the perfect graphs. Every [[induced subgraph]] of a Meyniel graph is another Meyniel graph, and in every Meyniel graph the size of a [[maximum clique]] equals the minimum number of colors needed in a [[graph coloring]]. Thus, the Meyniel graphs meet the definition of being a perfect graph, that the clique number equals the chromatic number in every induced subgraph.<ref name="isgci"/><ref name="m76"/><ref name="mk"/>

Meyniel graphs are also called the '''very strongly perfect graphs''', because (as Meyniel conjectured and Hoàng proved) they can be characterized by a property generalizing the defining property of the [[strongly perfect graph]]s: in every induced subgraph of a Meyniel graph, every vertex belongs to an [[independent set (graph theory)|independent set]] that intersects every [[maximal clique]].<ref name="isgci"/><ref>{{citation
 | last = Hoàng | first = C. T.
 | doi = 10.1016/0095-8956(87)90047-5
 | issue = 3
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 888682
 | pages = 302–312
 | series = Series B
 | title = On a conjecture of Meyniel
 | volume = 42
 | year = 1987| doi-access = free
 }}.</ref>

==Related graph classes==
The Meyniel graphs contain the [[chordal graph]]s, the [[parity graph]]s, and their subclasses the [[interval graph]]s, [[distance-hereditary graph]]s, [[bipartite graph]]s, and [[line perfect graph]]s.<ref name="isgci">[http://www.graphclasses.org/classes/gc_194.html Meyniel graphs], Information System on Graph Classes and their Inclusions, retrieved 2016-09-25.</ref>
[[File:House graph.svg|thumb|upright=0.65|The house graph is perfect but not Meyniel]]
Although Meyniel graphs form a very general subclass of the perfect graphs, they do not include all perfect graphs. For instance the house graph (a pentagon with only one chord) is perfect but is not a Meyniel graph.

==Algorithms and complexity==
Meyniel graphs can be recognized in [[polynomial time]],<ref>{{citation
 | last1 = Burlet | first1 = M.
 | last2 = Fonlupt | first2 = J.
 | contribution = Polynomial algorithm to recognize a Meyniel graph
 | doi = 10.1016/S0304-0208(08)72938-4
 | mr = 778765
 | pages = 225–252
 | publisher = North-Holland, Amsterdam
 | series = North-Holland Math. Stud.
 | title = Topics on perfect graphs
 | volume = 88
 | year = 1984| hdl = 10068/49205
 | hdl-access = free
 }}.</ref> and several graph optimization problems including [[graph coloring]] that are [[NP-hard]] for arbitrary graphs can be solved in polynomial time for Meyniel graphs.<ref>{{citation
 | last = Hertz | first = A.
 | doi = 10.1016/0095-8956(90)90078-E
 | issue = 2
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 1081227
 | pages = 231–240
 | series = Series B
 | title = A fast algorithm for coloring Meyniel graphs
 | volume = 50
 | year = 1990| doi-access = free
 }}.</ref><ref>{{citation
 | last1 = Roussel | first1 = F.
 | last2 = Rusu | first2 = I.
 | doi = 10.1016/S0012-365X(00)00264-8
 | issue = 1–3
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 1829840
 | pages = 107–123
 | title = An {{math|''O''(''n''<sup>2</sup>)}} algorithm to color Meyniel graphs
 | volume = 235
 | year = 2001| doi-access = free
 }}.</ref>

==References==
{{reflist}}

[[Category:Graph families]]
[[Category:Perfect graphs]]