Leírás
SZTE, TTIK, Bolyai Intézet, Kombinatorika szeminárium
Absztrakt. Thomassen a következőt sejtette: minden 3-összefüggő 3-reguláris gráfnak létezik olyan piros-kék csúcsszínezése, hogy a kék csúcsok által feszített részgráfban a maximális fokszám legfeljebb 1 (azaz egy független élhalmaz és izolált csúcsok uniója), és a piros csúcsok által feszített részgráf nem tartalmaz 3 élű utat, miközben a minimális fokszáma legalább 1. Az ilyen csúcsszínezést "morzsásnak" fogjuk nevezni. Nemrégiben Bellitto, Klimošová, Merker, Witkowski és Yuditsky a fenti sejtést megcáfolta, ugyanis mutattak ellenpéldáknak végtelen családját.
A konstrukcióik alapjául szolgáló segédgráfjuk 2-összefüggő síkgráf, ami tartalmaz $K_4$-minort és 5 hosszú kört is. Ezért a sejtés nyitott maradt még olyan fontos gráfcsaládokra mint például a külsíkgráfok, páros gráfok, $K_4$-minor mentes gráfok.
Az előadásomban szeretném vázolni, hogy milyen részeredményekre jutottunk a fent említett gráfosztályok esetén és megemlítenék néhány továbbra is nyitott kérdést. (az eredmények Barát Jánossal és Damásdi Gáborral közösek).