Tomasz JUSZCZYK

(UJ)

Pakowanie grafów - warunek typu Orego

Tematyką referatu będzie pakowanie grafów. Sauer i Spencer udowodnili, źe jeśli $2 \Delta(G_1) \Delta(G_2) < n$ to grafy $G_1$ i $G_2$ są pakowalne.

W referacie przedstawione zostaną uogólnienia typu Orego powyźszego twierdzenia. Omówię najnowsze wyniki Kostochki i Yu, którzy pokazali, źe $G_1$ i $G_2$ są pakowalne jeźeli $\mathit{\Theta(G_1)} \Delta(G_2) < n$, gdzie $\mathit{\Theta(G)}= \max \{d(u)+d(v): uv\in E(G)\}$. Podam takźe charakteryzację wszystkich niepakowalnych grafów $G_1$, $G_2$, dla których $\mathit{\Theta(G_1)} \Delta(G_2) = n$.

Serdecznie zapraszamy wszystkich chętnych !