| Abstrakt: | Farbenie grafov je jednou z najpopulárnejších oblastí, ktorou sa zaoberá te-
ória grafov. Farbenie grafu je priradenie farieb jednotlivým vrcholom, tak
aby susedné vrcholy mali rôzne farby. V tejto práci si bližšie predstavíme
zoznamové farbenie, ktoré je zovšeobecnením štandardného farbenia. V zo-
znamovom farbení má každý vrchol zoznam prípustných farieb, ktorými môže
byť ofarbený. Oboznámime čitateľa s hypotézou o zoznamovom farbení a s
doterajšími výsledkami o zoznamovom farbení a platnosti hypotézy o zo-
znamovom farbení. Ďalej v štvrtej kapitole predstavíme metódy dokazovaní
danej hypotézy spolu s názornými príkladmi, ktoré využívajú grafový poly-
nóm, orientácie grafu, permutácie a faktorizáciu. Následne v piatej kapitole
predvedieme dôkazy platnosti hypotézy o zoznamovom farbení pre koleso,
jeho modifikácie, zovšeobecnené Petersenove grafy kroku 1, Möbiov rebrík a
iné triedy.
|
|---|