Robert Lukoťka
Toto je zoznam tém, ktoré mám premyslené a pripravé. Okrem týchto tém sú k dispozícii ďalšie, ktoré ale vyžadujú určitú mieru diskusie.
Farebné množiny kubických 6-pólov (BP, DP)
Kubický 6-pól je graf obsahujúci vrcholy stupňa tri a jedna, pričom vrcholov strupňa jedna je presne 6, pričom vrcholy stupňa jedna sú usporiadané.
Označne si hrany incidenté s vrcholmi stupňa jedna postupne e_1, e_2, ..., e_6.
Zafarbenie kubického 6-pólu zobrazenie, ktoré hranám priradí hodnoty z množiny farieb {0, 1, 2}, tak, že susedné hrany nemajú rovnaké.
Hovorime, že pól umožňuje zafarbenie (a_1, a_2, ..., a_6) ak existuje farbenie pólu, také, Že e_i je zafarbené a_i.
Farebná množina pólu je množina zafrabení, ktoré pól umožňuje. Cieľom práce je skúmať, pre ktoré množiny 6-tíc existuje pól pre ktorý je táto množina farebnou množinou.
Očakávané nástroje: kombináciateoretického prístupu a počítačových experimentov
Algoritmy na určenie cirkulárneho chromatického indexu kubických grafov (DP)
Cirkulárne r-farbenie grafu je priradenie farieb hranám, pričom rozdiel farieb susedných hrán musí byť aspoň 1 modulo r. Cieľom práce je preskúmať možnosti na efektívny výpočet circulárneho chromatického indexu kubických a subkubických grafov.
Očakávané nástroje: zmiešané lineárne programovanie, základy topológie.
Nerepetitívne zoznamové farbenia ciest(BP, DP)
Majme cestu na n vrcholoch. Ku kazdemu vrcholu je priradeny zoznam 3 prirodzenych cisel. Hypotéza o zoznamovom nerepetitívnom farbení ciest hovorí, že je vždy možné zo zoznamov vybrať farby tak, že ziadnych 2k susedných vrcholov nebude ofarbených tak, že prvá polka postupnosti je ofarbená rovnako ako druhá polka. Cieľom práce je overiť túto hypotézu pre čo najväčšie n. Diplomová práca A. Stupala dokazuje hypotézu do 11 vrcholov.
Očakávané nástroje: hocico co pomôže, 15 vrcholov by bol úspech