Leírás
Egy digráf D aciklikus kromatikus száma az a minimális k
hogy D csúcsai fedhetőek k aciklikus halmazzal. Természetesen az
aciklikus kromatikus száma egy digráfnak lehet tetszőlegesen nagy;
számos híres sejtés a mai napig megoldatlan a témában:
(1) (Neumann-Lara) Igaz-e hogy minden síkba rajzolható digráf
aciklikus kromatikus száma legfeljebb 2.
(2) (Erdős, Neumann-Lara) Van-e f: N -> N függvény, hogy ha G gráf
kromatikus száma legalább f(n) akkor G éleinek van olyan D irányítása
hogy D aciklikus krom. száma legalább n.
A kérdés, amit mi vizsgálunk, az hogy mennyire lehet egy digráf
aciklikus kromatikus számát csökkenteni a következő egyszerű operáció
iterálásával: keressünk egy irányított kört majd fordítsuk meg az élek
írányítását a kör mentén. A sejtés a következő:
(3) (Thomassé) tetszőleges (véges vagy végtelen) D digráf aciklikus
krom. száma legfeljebb 2 egy megfelelő körfordítás sorozat után.
Az előadás célja, hogy prezentáljam az ismert eredményeket,
technikákat illetve a jelenleg nyitott eseteit a (3)-as kérdésnek.