Agnieszka Görlich

(WMS, AGH)

O pakowaniu grafów skierowanych

Jedno z klasycznych twierdzeń związanych z problematyką pakowania grafów mówi, że dowolny graf prosty rzędu n i rozmiaru nie większego niż n-2 jest pakowalny w swoje dopełnienie. Przykład gwiazdy pokazuje, że tego szacowania nie można poprawić.
Podejmowane były próby znalezienia maksymalnej wartości $f_D(n)$ takiej, że dowolny graf skierowany rzędu n i rozmiaru nie większego niż $f_D(n)$ jest pakowalny w swoje dopełnienie w grafie skierowanym pełnym. W 1985 roku Benhocine i Wojda postawili hipotezę, że graf skierowany rzędu n i rozmiaru nie większego niż 2n-4 jest podgrafem samodopełniającego grafu skierowanego rzędu n, a więc, w szczególności, jest grafem pakowalnym. Jak dotąd udało się pokazać, że $\frac{7}{4}n-81 \leq f_D(n) \leq 2n-4$, przy czym górnego ograniczenia rozmiaru pakowalnego grafu skierowanego nie można poprawić.
W trakcie referatu przedstawię wynik osiągnięty we współpracy z A. Żakiem, mówiący o tym, że $f_D(n) \geq 2n-o(n)$.

Serdecznie zapraszamy wszystkich chętnych !