zaver.tex

\chapter*{Záver}  % chapter* je necislovana kapitola
\addcontentsline{toc}{chapter}{Záver} % rucne pridanie do obsahu
\markboth{Záver}{Záver} % vyriesenie hlaviciek

V našej práci sme sa venovali problému $L(2,1)$-farbenia. Popísali sme spôsob, ktorým
môžeme problém $L(2,1)$-farbenia pre väčšinu prípadov zredukovať na problém $L(2,1)$-farbenia
na chlpatých $2$-hranovo súvislých grafoch. Taktiež sme ukázali konštrukciu
algoritmu na planárnych grafoch s časovou zložitosťou $O^*(2.2^{n + o(n)})$
a konštrukciu algoritmu na vyvážene rozdeliteľných grafoch s časovou zložitosťou
$O^*(2.613^n)$. Nakoniec sme ukázali algoritmus konštrukcie všetkých neoznačených
minimálne $2$-hranovo súvislých grafov.

Väčšina z predošlých efektívnych algoritmov riešiacich problém $L(2,1)$-farbenia
využívala reprezentáciu čiastočných farbení pomocou ich charakteristík. Najväčší
počet rôznych charakteristík, a teda aj najhoršiu časovú zložitosť, dosahovali
dobre rozdeliteľné grafy. V našej práci sme využili rozdeliteľnosť na konštrukciu
rýchlejšieho algoritmu pre problém $L(2,1)$-farbenia. Ďalší výskum problému
$L(2,1)$-farbení a podobných problémov by sa teda mohol venovať grafom, ktoré
nie sú vyvážene rozdeliteľné. Očakávame, že niektorý zo skorších
algoritmov, napr. Junosza-Szaniawski, by sa dal prispôsobiť, aby na takýchto
grafoch dosahoval lepšiu časovú zložitosť.

Ďalší možný smer výskumu je venovať sa $L(2,1)$-farbeniam $2$-hranovo
súvislých grafov, resp. chlpatých $2$-hranovo súvislých grafov. Predpokladáme,
že rýchly algoritmus pre problém $L(2,1)$-farbenia na tejto triede grafov
by sa dal prispôsobiť, aby rýchlo riešil problém na všeobecných grafoch.

Nakoniec postup generovania neoznačených minimálne $2$-hranovo súvislých
grafov nám dáva možnosť ďalej študovať túto triedu grafov. Jedným z využití
tohto postupu môže byť enumerácia neoznačených minimálne $2$-hranovo súvislých
grafov.