¿Referencia para gráficos libres de (agujero impar, anti agujero)?

Los gráficos sin X son aquellos que no contienen ningún gráfico de X como un subgrafo inducido. Un hoyo es un ciclo con al menos 4 vértices. Un agujero impar es un agujero con un número impar de vértices. Un antiagujero es el complemento de un agujero.

Los gráficos libres de (agujero impar, anti-agujero impar) son precisamente los gráficos perfectos; Este es el teorema del gráfico perfecto fuerte . Es posible encontrar el conjunto independiente más grande (y la camarilla más grande) en un gráfico perfecto en tiempo polinómico, pero el único método conocido para hacerlo requiere construir un programa semi-definido para calcular el número theta de Lovász .

Los gráficos libres de agujeros (antihoyo) se denominan débilmente cordal y constituyen una clase bastante fácil para muchos problemas (incluidos SET INDEPENDIENTE y CLIQUE ).

¿Alguien sabe si se han estudiado o escrito gráficos sin agujeros (anti-agujero, anti-agujero)?

Estas gráficas ocurren de forma bastante natural en problemas de satisfacción de restricciones donde la gráfica de variables relacionadas forma un árbol. Tales problemas son bastante fáciles, por lo que sería bueno si hubiera una forma de encontrar una camarilla de conjuntos independientes más grande para gráficos en esta familia sin tener que calcular la theta de Lovász.

De manera equivalente, uno quiere encontrar un conjunto independiente más grande para gráficos libres de agujeros (agujeros, anti agujeros). Hsien-Chih Chang señala a continuación por qué esta es una clase más interesante para SET INDEPENDIENTE que los gráficos sin agujeros (anti-agujero, anti-agujero).

De hecho, es relativamente fácil. En cambio, para estudiar el problema del conjunto independiente en gráficos libres de agujeros (impares, antiagujeros), tomamos el complemento de los gráficos e intentamos encontrar una camarilla máxima en él. Por lo tanto, se convierte en un problema de camarilla máxima en los gráficos sin agujeros (agujero, anti-agujero extraño).

En la sección 2 del documento " Barrios triangulados en gráficos sin agujeros pares " de da Silva y Vuskovic, declararon que Farber muestra por primera vez

$O(n^2)$

Entonces su teorema principal declaró que

$O(n + m)$ camarillas máximas en gráficos libres de agujeros pares, y todas las camarillas máximas se pueden encontrar a tiempo$O(n^2m)$.

Como estamos tratando con gráficos sin agujeros (agujeros, anti-agujeros impares) que están claramente libres de agujeros pares, encontrar una camarilla máxima toma como máximo $O(n^2m)$ hora.

Los 4 agujeros libres son críticos para este tipo de resultados, como un algoritmo de poli-tiempo para $\overline{K_{2,m}}$sin gráficos, por lo que el verdadero desafío puede ser estudiar el problema del conjunto independiente en gráficos libres de (agujero, anti-agujero extraño), que se convierte en el problema de la camarilla máxima en los gráficos libres de (agujero, anti-agujero).

Editar:

Oh, surgió otro pensamiento. Los gráficos libres de agujeros (anti-agujeros impares) son casi débilmente cordales en el siguiente sentido: dado que 4 agujeros libres implica que solo quedan anti-agujeros con un tamaño de 4 ~ 7 (cualquier k-anti-agujero con tamaño> 7 contiene 4 agujeros), y también está libre de agujeros extraños, lo que restringe el tamaño de los agujeros a 4 y 6, ¡casi no hay agujeros / agujeros en el gráfico! Por lo tanto, un algoritmo de poli-tiempo parece plausible para tales gráficos.