Description
Egy teljes gráf éleit színezzük 2 színnel. Ismert, hogy ekkor található monokromatikus feszítőfa. Hány csúcsú teljes gráfot kell venni ahhoz, hogy m élű monokromatikus párosítást találjunk? Mi ismert más részstruktúrákra? Utakra, körökre.
Tekinthetjük a fenti problémákat geometriai gráfokon vagy topológikus gáfokon. Ekkor olyan monokromatikus részeket keresünk, melynek élei páronként nem metszők. Ennek egy speciális esete a twisted gráf, mikor a lehető legtöbb metszéssel van lerajzolva az alapgráf. Ez vezetett el minket arra, hogy a kérdést rendezett csúcshalmazon vizsgáljuk.
Vegyünk az 1,2...,k rendezett halmazon egy teljes gráfot. Két él kölcsönös helyzete háromféle lehet: szeparált, metsző vagy ölelkező. Ezek alapján 6-féle megszorítást tehetünk a keresett monokromatikus részstruktúrára. Ezekről a kérdésekről fogok beszélni.
Közös eredmények Gyárfás Andrással, Tóth Gézával