Antecedentes: Sea dos vértices de un gráfico no dirigido . Un conjunto de vértices es un separador si y pertenecen a diferentes componentes conectados de . Si no hay un subconjunto adecuado de -separator es un -separator, entonces es un mínimo -separator. Un conjunto de vértices es un separador (mínimo) si existen vértices modo que sea un separador (mínimo) .
Un conocido teorema de G. Dirac afirma que un gráfico no tiene ciclos inducidos de longitud de al menos cuatro (llamado gráfico triangulado o cordal) si y solo si cada uno de sus separadores mínimos es una camarilla. También es bien sabido que los gráficos triangulados se pueden reconocer en el tiempo polinomial.
Mis preguntas: ¿Qué son los gráficos en los que cada separador mínimo es un conjunto independiente? ¿Se estudian estos gráficos? ¿Y cuál es la complejidad de reconocimiento de estos gráficos? Los ejemplos de tales gráficos incluyen árboles y ciclos.
fuente