Steinerovské farbenia kubických grafov

Študentská vedecká konferencia 2004 Dávid Pál, FMFI UK

Abstrakt

Farbenie kubického grafu pomocou steinerovského systému trojíc je farbenie jeho hrán tak, aby farby každej trojice hrán majúcej spoločný vrchol tvorili trojicu steinerovského systému. Hlavným výsledkom mojej práce je, že kubické grafy bez sériovo-paralelného konca (t.j. všetky steinerovsky zafarbiteľné grafy vôbec) sú zafarbiteľné steinerovským sýstemom AG(1, 3) × P G(2, 2) rádu 21. Ďalej sa podarilo úplne charakterizovať triedu kubických grafov zafarbiteľných afínnymi steinerovskými systémami AG(n, 3) pre n ≥