Názov projektu: Rovnomerné hranové farbenia kubických grafov
Meno študenta: Lukáš Hudcovský
Email: hudcovsky4@uniba.sk
Školiteľ: doc. RNDr. Edita Mačajová, PhD.
Email: macajova@dcs.fmph.uniba.sk
Špecifikácia projektu: V roku 2013, Fronček vyslovil hypotézu,
že hrany ľubovoľného kubického grafu sa dajú
zafarbiť tromi farbami tak, že pri každom vrchole sa stretávajú buď hrany
troch rôznych farieb alebo sa všetky tri farby
zhodujú a celkový počet hrán zafarbených jednotlivými farbami je
rovnaký. Je zrejmé, že táto hypotéza je pravdivá pre
grafy, ktoré majú hranové regulárne 3-zafarbenie, na množine snarkov
je však otvorená a málo prebádaná.
Úlohou študenta bude navrhnúť a implementovať algoritmus na potvrdenie
či vyvrátenie tejto hypotézy, prípadne jej
zosilnení a otestovať vygenerované snarky (kubické grafy bez hranového
3-zafarbenia) do čo najväčšieho počtu vrcholov.
Taktiež teoretickými tvrdeniami vylúčiť niektoré typy protipríkladov.