| Abstrakt: | Práca sa zaoberá Kempe-grafmi farbení, najmä Kempe-ekvivalentnosťou hranových farbení kubických grafov. Najprv si zavedieme všeobecné pojmy z teórie grafov a následne tiež pojmy Kempe-prepnutie, graf farbení, Kempe-ekvivalencia.
V ďalšom texte ukážeme niekoľko teoretických výsledkov o grafoch farbení odvodených z farbenia hrán kubických grafov, ktoré sú už známe a boli publikované v článku Bojana Mohara Kempe equivalence of colorings.
Nasleduje popis algoritmov, ktoré sme používali na generovanie grafov farbení a testovanie parametrov.
V ďalšej kapitole vyslovíme a dokážeme niekoľko tvrdení o grafoch farbení, napr. odhad stupňov vrcholov. Vďaka niektorým je možné vylepšiť efektivitu algoritmov. Tiež sme sa snažili pochopiť a zjednodušiť pohľad na štruktúru grafov farbení pomocou rozdelenia množiny vrcholov na také triedy, že nimi indukované podgrafy sú navzájom izomorfné.
V poslednej kapitole sme reagovali na problém uvedený v Moharovom Kempe equivalence of colorings, ktorý znie: "Pre ktoré kubické bipartitné grafy G je graf hranových 3-farbení súvislý?" a ukázali sme, že podmienky, ktoré stanovil Fisk, vo svojom dôkaze špeciálneho prípadu nie sú nutné.
|
|---|