Antecedentes: Deixe- ser dois vértices de um grafo não direcionado G = ( V , E ) . Um conjunto vértice S ⊆ V é um u , v -separator se u e v pertencem a diferentes componentes ligados de L - S . Se nenhum subconjunto adequado de um u , v -separator S for u , v -separator, então S será um mínimo u , v-separador. Um conjunto de vértices é um separador (mínimo) se existirem vértices u , v de modo que S seja um (mínimo) u , v- separador.
Um teorema bem conhecido de G. Dirac afirma que um gráfico não tem ciclos de comprimento induzidos pelo menos quatro (chamado gráfico triangular ou cordal) se e somente se cada um de seus separadores mínimos for um clique. Também é sabido que gráficos triangulados podem ser reconhecidos em tempo polinomial.
Minhas perguntas: Quais são os gráficos nos quais todo separador mínimo é um conjunto independente? Estes gráficos são estudados? E qual é a complexidade de reconhecimento desses gráficos? Exemplos para esses gráficos incluem árvores e ciclos.
fonte