Morfológia nezafarbitelných 5-regulárnych grafov
Meno študenta:
Martin Križan
Mail:
krizan68@uniba.sk
Meno školitela:
RNDr. Ján Mazák, PhD
Mail:
mazak at dcs.fmph.uniba.sk
Názov projektu:
Morfológia nezafarbitelných 5-regulárnych grafov
Github:
https://github.com/MartinKrizan/morpology_of_five_regular_edge_uncolorable_graphs
Report ZS:
https://github.com/MartinKrizan/morpology_of_five_regular_edge_uncolorable_graphs/blob/main/RP-Report%20ZS.pdf
Ciele projektu:
Zima:
Vytvorenie zoznamu nezafarbitelnych 5-regulárnych grafov aspoň po 12 vrcholov, idealne viac
Ad-hoc analýza najmenších nezafarbitelnych grafov (pomocou obrázkov, ručného a počítačoveho backtrackingu apod.)
Identifikovanie príčin, prečo su tieto grafy nezafarbitelne, a ich generalizacia
Návrh automatizovaneho rozpoznávania grafov, ktoré su nezafarbitelne z príčiin identifikovanych vyššie
Leto:
Implementácia automatizovaného nástroja na rozpoznávanie príčin nezafarbitelnosti
Analýza kompletnych zoznamov grafov na čo najvačšom počte vrcholov (budú ich potencialne tisice az miliony)
Analýza vplyvu prítomnosti malych rezov na nezafarbitelnost