Estructura de gráficos que excluyen una coincidencia perfecta en cuatro vértices como un gráfico inducido

Estoy interesado en comprender la estructura de la clase de gráficos modo que no exista un subgrafo inducido por vértices en cuatro vértices que coincida perfectamente. Dicho de manera diferente para cualquier cuatro vértices en si y son bordes, entonces el gráfico debe tener al menos un borde más en los cuatro vértices. ¿Esta clase ha sido estudiada previamente? Cualquier referencia o idea sería apreciada. Entendemos esta clase cuando se restringe a gráficos bipartitos, pero el caso general parece más complicado. $G$ $a,b,c,d$ $G$ $ab$ $cd$

graph-theory Chandra Chekuri
fuente

Desea agregar aquí una propiedad importante de los gráficos libres de

, a saber, que el número de conjuntos independientes máximos en dichos gráficos es polinómico en el número de vértices. De hecho, para cualquier gráfico libre de

libre tiene un número polinómico de conjuntos independientes máximos. Consulte la siguiente referencia para obtener más información. "La complejidad resulta en gráficos con pocas camarillas". Matemáticas discretas y ciencias de la computación teórica 9.1 (2007): 127-135.

2 K_{2}

$2K_2$

t

$t$

t K_{2}

$tK_2$

Chandra Chekuri

Estructura de gráficos que excluyen una coincidencia perfecta en cuatro vértices como un gráfico inducido

Respuestas: