Antoni MARCZYK

(WMS, AGH)

Warunki typu Orego dla dowolnej podzielności

Graf $G$ jest dowolnie rozkładalny, jeśli dla dowolnego ciągu $a_1,\ldots,a_k$ liczb naturalnych dających w sumie rząd grafu moźna znależć podział $V_1,\ldots,V_k$ zbioru wierzchołków o licznościach odpowiednio $a_1,\ldots,a_k$ i takich źe kaźdy zbiór $V_i$ indukuje podgraf spójny grafu $G$. Oczywiście kaźdy graf trasowalny (tzn. mający ścieźkę Hamiltona) jest dowolnie rozkładalny, zatem dowolna rozkładalność jest warunkiem słabszym niź trasowalność. Stąd wniosek, źe jeźeli graf $G$ rzędu $n$ spełnia warunek typu Orego $\sigma_2(G)\ge n-1$, to jest on dowolnie rozkładalny. W trakcie referatu omówiony zostanie wynik, stwierdzający, źe jeśli $G$ jest grafem spójnym o dostatecznie duźym rzędzie spełniającym warunek $\sigma_2(G)\ge n-5$, to dowolna rozkładalność jest równowaźna istnieniu skojarzenia pełnego (lub prawie-pelnego).

Serdecznie zapraszamy wszystkich chętnych !