Estrutura de gráficos que excluem uma correspondência perfeita em quatro vértices como um gráfico induzido

13

Estou interessado em entender a estrutura da classe dos gráficos modo que não exista subgráfico induzido por vértices em quatro vértices, o que é uma correspondência perfeita. Dado de forma diferente para quaisquer quatro vértices a , b , c , d em G se a b e c d são arestas, o gráfico deve ter pelo menos mais uma aresta nos quatro vértices. Essa classe foi estudada anteriormente? Quaisquer referências ou idéias serão apreciadas. Entendemos essa classe quando restrita a gráficos bipartidos, mas o caso geral parece mais complicado.Guma,b,c,dGumabcd

Chandra Chekuri
fonte
Quer acrescentar aqui uma importante propriedade dos gráficos -free, ou seja, que o número de conjuntos independentes máximas em tais gráficos é polinomial no número de vértices. De fato, para qualquer fixo t t K 2 -livre gráficos Tem um polinômio número de conjuntos independentes máximos. Veja ref a seguir para mais informações. "A complexidade resulta em gráficos com poucas panelinhas." Matemática Discreta e Ciência da Computação Teórica 9.1 (2007): 127-135. 2K2t tK2
Chandra Chekuri

Respostas: