Struktura wykresów wykluczająca idealne dopasowanie na czterech wierzchołkach jako wykres indukowany

Interesuje mnie zrozumienie struktury klasy grafów taki sposób, że na czterech wierzchołkach nie ma podgraphu indukowanego wierzchołkiem, który jest idealnym dopasowaniem. Zaznaczono inaczej, dla wszystkich czterech wierzchołkach , w jeśli i są krawędzie to wykres powinien posiadać co najmniej jedną krawędź w czterech wierzchołkach. Czy ta klasa była wcześniej badana? Wszelkie referencje lub spostrzeżenia będą mile widziane. Rozumiemy tę klasę, gdy ograniczamy się do grafów dwustronnych, ale ogólny przypadek wydaje się trudniejszy. $G$ $a,b,c,d$ $G$ $ab$ $cd$

graph-theory

— Chandra Chekuri
źródło

Chciałbym tutaj dodać ważną właściwość grafów wolnych od

, a mianowicie to, że liczba maksymalnych niezależnych zbiorów na takich grafach jest wielomianowa w liczbie wierzchołków. W zasadzie stałe dla każdego

-Darmowy wykresy Posiadane wielomianem liczba niezależnych maksymalnych zbiorów. Aby uzyskać więcej informacji, patrz poniższy odnośnik. „Wyniki złożoności na wykresach z kilkoma klikami”. Matematyka dyskretna i informatyka teoretyczna 9.1 (2007): 127-135.

2 K_{2}

$2K_2$

t

$t$

t K_{2}

$tK_2$

— Chandra Chekuri,