Conjuntos independientes máximos / máximos

¿Se sabe algo sobre la clase de gráficos con la propiedad de que todos los conjuntos independientes máximos tienen la misma cardinalidad y, por lo tanto, son IS máximos?

Por ejemplo, tome un conjunto de puntos en el plano y considere la gráfica de intersecciones entre todos los segmentos entre pares de puntos en el conjunto. (segmentos-> vértices, intersecciones-> bordes). Este gráfico tendrá la propiedad anterior, ya que todos los IS máximos corresponden a triangulaciones del conjunto de puntos original. ¿Hay otras categorías de gráficos que tengan esta propiedad? ¿Se puede probar esta propiedad fácilmente?

Tales gráficos se llaman gráficos bien cubiertos . Aquí hay un artículo reciente sobre el tema que enumera varias referencias útiles. Como mencionó Suresh, el problema de reconocimiento es co-NP-completo.

Tenga en cuenta que los conjuntos independientes de un gráfico forman un complejo simplicial abstracto. Los complejos simples que surgen de esta manera se denominan "complejos de independencia" o "complejos de bandera". Se dice que un complejo simplicial es puro si cada simplex máximo tiene la misma cardinalidad. Por lo tanto, puede encontrar algunos documentos relevantes buscando "complejo de independencia pura" o "complejo de bandera pura".

La propiedad MAXIMAL = MAXIMUM para conjuntos independientes en gráficos y estructuras combinatorias más generales es importante. Será interesante comprender los gráficos en los que esta propiedad es válida para todos los subgráficos inducidos. Un caso abstracto general donde tenemos MAXIMUM = MAXIMAL es cuando hay una estructura matroide subyacente, pero hay muchos otros casos, como el caso de los gráficos planos máximos mencionados en la pregunta. Aquí hay un ejemplo relacionado: considere n puntos en el plano en posición convexa y deje que k sea un número entero. Considere los gráficos cuyos vértices son segmentos de línea entre estos puntos donde dos vértices son adyacentes si los segmentos de línea no se cruzan. Dress demostró que para este gráfico MAXIMIM = MAXIMAL para conjuntos independientes.