Ročníkový Projekt

Názov projektu: Morfológia nezafarbiteľných 4-regulárnych grafov


Meno študenta: Matúš Buček

Kontakt na študenta: bucek33@uniba.sk


Meno školiteľa: doc. RNDr. Ján Mazák, PhD.

Kontakt na školiteľa: jan.mazak@fmph.uniba.sk


GitHub


Plán

Zimný semester

Vytvorenie zoznamu nezafarbiteľných 4-regulárnych grafov aspoň po 17 vrcholov, ideálne viac

Ad-hoc analýza najmenších nezafarbiteľných grafov (pomocou obrázkov, ručného a počítačového backtrackingu apod.)

Identifikovanie príčin, prečo sú tieto grafy nezafarbiteľné, a ich generalizácia

Návrh automatizovaného rozpoznávania grafov, ktoré sú nezafarbiteľné z príčin identifikovaných vyššie

Report za zimný semester



Letný semester

Implementácia automatizovaného nástroja na rozpoznávanie príčin nezafarbiteľnosti

Analýza kompletnych zoznamov grafov na čo najväčšom počte vrcholov (budú ich potenciálne tisíce až milióny)

Analýza vplyvu prítomnosti malých rezov na nezafarbiteľnosť