Andrzej Żak

(WMS AGH)

Pakowanie grafów bez krótkich cykli o ograniczonym rozmiarze

Niech $T_k$ oznacza następujące zdanie:

Kazdy graf o talii (girth) $g > k$ jest podgrafem swojego dopełnienia.

W 1981 r. Faudree, Rousseau, Schelp i Schuster postawili hipoteze, ze zachodzi $T_4$. Jak dotad wiadomo, ze zachodzi $T_5$ (Görlich, Zak 2009). Zatem $T_4$ zachodzi dla grafów dwudzielnych. Wiadomo tez, ze $T_4$ zachodzi dla grafów o rozmiarze $\vert\vert G\vert\vert\leq \frac{6}{5}\vert G\vert-2$ (Faudree, Rousseau, Schelp i Schuster 1981). Podczas referatu zostanie przedstawiony wynik osiagniety wspólnie z A. Görlich i mówiacy, ze $T_4$ zachodzi dla grafów o rozmiarze $\vert\vert G\vert\vert\leq 2n-o(n)$, gdzie n oznacza rzad grafu. Wynika stad w szczególnosci, ze $T_4$ zachodzi dla wszystkich dostatecznie duzych grafów planarnych.

Serdecznie zapraszamy wszystkich chętnych !