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 in which every odd cycle of length five or more has at least two chords (edges connecting non-consecutive vertices of the cycle). long before the proof of the strong perfect graph theorem completely characterized the perfect graphs.
The same result was independently discovered by .
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.
Related graph classes
The Meyniel graphs contain the chordal graphs, the parity graphs, and their subclasses the interval graphs, distance-hereditary graphs, bipartite graphs, and line perfect graphs.
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, and several graph optimization problems including graph coloring that are NP-hard for arbitrary graphs can be solved in polynomial time for Meyniel graphs.