graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a Meyniel graph is a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

in which every odd

cycle Cycle, cycles, or cyclic may refer to: Anthropology and social sciences * Cyclic history, a theory of history * Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr. * Social cycle, various cycles in ...

of length five or more has at least two

chords Chord or chords may refer to: Art and music * Chord (music), an aggregate of musical pitches sounded simultaneously ** Guitar chord, a chord played on a guitar, which has a particular tuning * The Chords (British band), 1970s British mod ...

(edges connecting non-consecutive vertices of the cycle). 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 Meyniel's conjecture), who proved that they are

perfect graph In graph theory, a perfect graph is a Graph (discrete mathematics), graph in which the Graph coloring, chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic nu ...

s in 1976,. long before the proof of the

strong perfect graph theorem In graph theory, the strong perfect graph theorem is a forbidden graph characterization of the perfect graphs as being exactly the graphs that have neither odd holes (odd-length induced cycles of length at least 5) nor odd antiholes (complements o ...

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 In graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges, from the original graph, connecting pairs of vertices in that subset. Definition Formally, let G=(V,E) ...

of a Meyniel graph is another Meyniel graph, and in every Meyniel graph the size of a

maximum clique In graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is complete. Cliques are one of th ...

equals the minimum number of colors needed in a

graph coloring In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a Graph (discrete mathematics), graph. The assignment is subject to certain constraints, such as that no two adjacent elements have th ...

. Thus, the Meyniel graphs meet the definition of being a perfect graph, that the clique number equals the chromatic number in every induced subgraph. 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 This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges. Symbols A B ...

s: in every induced subgraph of a Meyniel graph, every vertex belongs to an independent set that intersects every

maximal clique In graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is complete. Cliques are one of t ...

Related graph classes

The Meyniel graphs contain the chordal graphs, the

parity graph In graph theory, a parity graph is a graph in which every two induced paths between the same two vertices have the same parity: either both paths have odd length, or both have even length.

s, and their subclasses the

interval graph In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals. In ...

distance-hereditary graph In graph theory, a branch of discrete mathematics, a distance-hereditary graph (also called a completely separable graph) is a graph in which the Distance (graph theory), distances in any connected graph, connected induced subgraph are the same as ...

bipartite graph In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...

s, and

line perfect graph In graph theory, a line perfect graph is a graph whose line graph is a perfect graph. Equivalently, these are the graphs in which every odd-length simple cycle is a triangle. A graph is line perfect if and only if each of its biconnected compone ...

s.Meyniel graphs
Information System on Graph Classes and their Inclusions, retrieved 2016-09-25.

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 In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...

, and several graph optimization problems including

that are

NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...

for arbitrary graphs can be solved in polynomial time for Meyniel graphs..

References

{{reflist Graph families Perfect graphs