En teoría de grafos , un grafo de Meyniel es un grafo en el que cada ciclo impar de longitud cinco o más tiene al menos dos cuerdas (aristas que conectan vértices no consecutivos del ciclo). [1] Las cuerdas pueden no estar cruzadas (como se muestra en la figura) o pueden cruzarse entre sí, siempre que haya al menos dos de ellas.
Los grafos de Meyniel reciben su nombre de Henri Meyniel (también conocido por la conjetura de Meyniel ), quien demostró que son grafos perfectos en 1976, [2] mucho antes de que la prueba del teorema fuerte de grafos perfectos caracterizara por completo a los grafos perfectos. El mismo resultado fue descubierto independientemente por Markosjan y Karapetjan (1976). [3]
Los grafos de Meyniel son una subclase de los grafos perfectos. Cada subgrafo inducido de un grafo de Meyniel es otro grafo de Meyniel, y en cada grafo de Meyniel el tamaño de una camarilla máxima es igual al número mínimo de colores necesarios en un grafo coloreado . Por lo tanto, los grafos de Meyniel cumplen con la definición de ser un grafo perfecto, en el sentido de que el número de camarillas es igual al número cromático en cada subgrafo inducido. [1] [2] [3]
Los grafos de Meyniel también se denominan grafos muy fuertemente perfectos , porque (como Meyniel conjeturó y Hoàng demostró) pueden caracterizarse por una propiedad que generaliza la propiedad definitoria de los grafos fuertemente perfectos : en cada subgrafo inducido de un grafo de Meyniel, cada vértice pertenece a un conjunto independiente que interseca cada camarilla máxima . [1] [4]
Los grafos de Meyniel contienen los grafos cordales , los grafos de paridad y sus subclases: los grafos de intervalo , los grafos hereditarios de distancia , los grafos bipartitos y los grafos de línea perfecta . [1]
Aunque los grafos de Meyniel forman una subclase muy general de los grafos perfectos, no incluyen todos los grafos perfectos. Por ejemplo, el grafo de la casa (un pentágono con una sola cuerda) es perfecto pero no es un grafo de Meyniel.
Los gráficos de Meyniel se pueden reconocer en tiempo polinomial , [5] y varios problemas de optimización de gráficos, incluida la coloración de gráficos que son NP-difíciles para gráficos arbitrarios, se pueden resolver en tiempo polinomial para gráficos de Meyniel. [6] [7]