The Meinel graph is a graph in which any odd cycle of length five or more has at least two chords, that is, two edges connecting the non-adjacent vertices of the cycle [1] . Chords can be disjoint (as in the picture), or they can intersect.
Meinel graphs are named after Henry Meinel (also known by the Meinel hypothesis ), who proved in 1976 that they are perfect graphs [2] long before the proof of the strong hypothesis of perfect graphs that completely describes perfect graphs. The same result was independently discovered by Markosyan and Karapetyan [3] .
Content
Perfection
Meinel graphs are a subclass of perfect graphs. Any generated subgraph of the Meinel graph is another Meinel graph, and in any Meinel graph the size of the largest clique is equal to the least number of colors needed to color the graph . Thus, Meinel graphs satisfy the definition of perfect graphs that the clique number is equal to the chromatic number in any generated subgraph [1] [2] [3] .
Meinel graphs are also called very strongly perfect graphs , because (as Meinel suggested and proved Hlang) they can be described by a property that generalizes the definition of the property of strictly perfect graphs - in any generated subgraph of the Meinel graph, any vertex belongs to an independent set that intersects with any maximal clique [ 1] [4] .
Related Graph Classes
Meinel graphs contain chordal graphs , parity graphs and their subclasses, interval graphs , distance-inherited graphs , bipartite graphs, and edge-perfect graphs [1] .
Although Meinel graphs form a very general subclass of graphs, they do not include all perfect graphs. For example, a house (a pentagon with one chord) is perfect, but it is not a Meinel graph.
Algorithms and Complexity
Meinel graphs can be recognized in polynomial time [5] and some optimization problems on graphs, including coloring graphs that are NP-hard for arbitrary graphs, can be solved in polynomial time for Meinel graphs [6] [7] .
Notes
- ↑ 1 2 3 4 Meyniel graphs , Information System on Graph Classes and their Inclusions, retrieved 2016-09-25.
- ↑ 1 2 Meyniel, 1976 , p. 339–342.
- ↑ 1 2 Markosyan, Karapetyan, 1976 , p. 292-296.
- ↑ Hoàng, 1987 , p. 302-312.
- ↑ Burlet, Fonlupt, 1984 , p. 225–252.
- ↑ Hertz, 1990 , p. 231–240.
- ↑ Roussel, Rusu, 2001 , p. 107-123.
Literature
- Meyniel H. On the perfect graph conjecture // Discrete Mathematics . - 1976. - T. 16 , no. 4 . - S. 339–342 . - DOI : 10.1016 / S0012-365X (76) 80008-8 .
- S. Markosyan, I. Karapetyan. On perfect graphs // DAN Arm. SSR. - 1976. - Vol. 5 .
- Hoàng CT On a conjecture of Meyniel // Journal of Combinatorial Theory . - 1987. - T. 42 , no. 3 . - S. 302-312 . - DOI : 10.1016 / 0095-8956 (87) 90047-5 .
- Burlet M., Fonlupt J. Polynomial algorithm to recognize a Meyniel graph // Topics on perfect graphs. - North-Holland, Amsterdam, 1984. - T. 88. - S. 225–252. - (North-Holland Math. Stud.). - DOI : 10.1016 / S0304-0208 (08) 72938-4 .
- Hertz A. A fast algorithm for coloring Meyniel graphs // Journal of Combinatorial Theory . - 1990. - T. 50 , no. 2 . - S. 231–240 . - DOI : 10.1016 / 0095-8956 (90) 90078-E .
- Roussel F., Rusu I. An O ( n 2 ) algorithm to color Meyniel graphs // Discrete Mathematics . - 2001. - T. 235 , no. 1-3 . - S. 107–123 . - DOI : 10.1016 / S0012-365X (00) 00264-8 .