Gráfico de Meyniel

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 cruzarse (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 demostración del teorema del grafo perfecto fuerte caracterizara completamente 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. Todo subgrafo inducido de un grafo de Meyniel es otro grafo de Meyniel, y en todo grafo de Meyniel el tamaño de una camarilla máxima es igual al número mínimo de colores necesarios para colorear un grafo . Por lo tanto, los grafos de Meyniel cumplen la definición de grafo perfecto, ya que el número de camarillas es igual al número cromático en todo 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ó) se pueden caracterizar 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 clique maximal . ^{[ 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 perfectos de línea . ^{[ 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 grafos de Meyniel se pueden reconocer en tiempo polinomial , ^{[ 5 ]} y varios problemas de optimización de grafos, incluyendo la coloración de grafos , que son NP-difíciles para grafos arbitrarios, se pueden resolver en tiempo polinomial para grafos de Meyniel. ^{[ 6 ] [ 7 ]}