Pap Gyula: A k-linkeltség elégséges tulajdonságairól

EGERVÁRY SZEMINÁRIUM

Absztrakt: Egy irányítatlan gráfot $k$-linkeltnek nevezünk, ha bármely $2k$ darabpontjára, $x_1, y_1, x_2, y_2, ... ,x_k, y_k$-ra igaz az, hogy létezik$k$ darab pontdiszjunkt út a megfelelő $x_i, y_i$ pontpárok közt.Bollobás és Thomason eredménye szerint bármely 22k-összefüggő gráfk-linkelt. Thomassen és Seymour karakterizálták a 2-linkelt gráfokat.Chen et al. belátták, hogy egy 6-összefüggő gráfban van $K_9^-$ minorakkor a gráf 3-linkelt. Ez utóbbi eredménynek egy erősítésétbizonyította be Maezawa amikor belátta, hogy ha $k\ge 3$ esetén egy2k-összefüggő gráfban létezik $K_{3k}^{-M?k}$ minor, akkor a gráfk-linkelt. Az előadásban ezekről, és úgy általában a k-linkeltségelégséges feltételeiről lesz szó.