Referência para gráficos livres de orifícios ímpares e anti-orifícios?

Gráficos livres de X são aqueles que não contêm gráfico de X como um subgrafo induzido. Um buraco é um ciclo com pelo menos 4 vértices. Um buraco ímpar é um buraco com um número ímpar de vértices. Um anti - furo é o complemento de um buraco.

Os gráficos livres de orifícios ímpares e orifícios ímpares são precisamente os gráficos perfeitos; esse é o teorema do gráfico perfeito forte . É possível encontrar o maior conjunto independente (e a maior clique) em um gráfico perfeito em tempo polinomial, mas o único método conhecido para fazer isso exige a construção de um programa semidefinido para calcular o número teta de Lovász .

Os gráficos livres de orifícios (anti furo) são chamados de cordas fracamente e constituem uma classe bastante fácil para muitos problemas (incluindo INDEPENDENT SET e CLIQUE ).

Alguém sabe se foram estudados ou escritos gráficos livres de buracos estranhos e anti-buracos?

Esses gráficos ocorrem naturalmente em problemas de satisfação de restrições, nos quais o gráfico de variáveis ​​relacionadas forma uma árvore. Tais problemas são bastante fáceis, por isso seria bom se houvesse uma maneira de encontrar uma maior clique independente de conjunto de gráficos nessa família sem precisar calcular o teta de Lovász.

Equivalentemente, deseja-se encontrar um maior conjunto independente para gráficos livres de furos (anti-furo). Hsien-Chih Chang mostra abaixo por que essa é uma classe mais interessante para o CONJUNTO INDEPENDENTE do que os gráficos livres de buracos ímpares e anti-buracos.

De fato, é relativamente fácil. Em vez de estudar o problema do conjunto independente em gráficos sem orifícios (anti-furo), pegamos um complemento dos gráficos e tentamos encontrar um clique máximo nele. Assim, torna-se o problema máximo de clique em gráficos sem orifícios (orifícios, orifícios ímpares).

Na seção 2 do artigo " Bairros triangulados em gráficos sem buracos ", de Silva e Vuskovic, eles afirmaram que Farber mostra pela primeira vez

$O(n^2)$

Então, seu principal teorema afirmou que

$O(n + m)$$O(n^2m)$

$O(n^2m)$

$\overline{K_{2,m}}$

Editar:

Oh, outro pensamento surgiu. Os gráficos sem furos (furos, furos anti-ímpares) são quase fracamente cordais no seguinte sentido: uma vez que livre de 4 furos implica apenas restos anti-furos com tamanho 4 ~ 7 (qualquer k-anti-furo com tamanho> 7 contém um orifício de 4) e também é livre de orifícios estranhos, o que restringe o tamanho dos orifícios a 4 e 6; quase não há orifícios / anti furos no gráfico! Assim, um algoritmo poli-tempo parece plausível para tais gráficos.