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 a , b , c , d en G si a b y c d 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.
graph-theory
Chandra Chekuri
fuente
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 t t K 2 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.
Chandra Chekuri