| Meno: | Alojz
|
|---|
| Priezvisko: | Stúpal
|
|---|
| Názov: | Nerepetitívne zoznamové farbenia ciest
|
|---|
| Vedúci: | doc. RNDr. Robert Lukoťka, PhD.
|
|---|
| Rok: | 2021
|
|---|
| Kľúčové slová: | nerepetitívnosť, zoznamovosť, farbenie, cesta, graf
|
|---|
| Abstrakt: | V práci sa snažíme čiastočne dokázať hypotézu pi_ch (P_n) = 3 pre každú cestu P_n, n >= 4, a teda overiť, že pre každú cestu o dĺžke aspoň štyri a pre každé priradenie zoznamov o troch farbách ku každému vrcholu na tejto ceste je možné nájsť aspoň jedno nerepetitívne farbenie, pričom každému vrcholu priradíme farbu z jemu prislúchajúcemu zoznamu. Nerepetitívne farbenie je také vrcholové farbenie grafu, že pre každú jeho podpostupnosť párnej dĺžky sa postupnosť farieb prvej polovice tejto podpostupnosti nezhoduje s postupnosťou farieb druhej polovice. Hypotézu dokážeme za pomoci značne zoptimalizovaného programu, a to pre všetky cesty s dĺžkou menšou alebo rovnou číslu 10. Hypotézu dokážeme s obmedzením na počet možných farieb pre zoznamy vrcholov i pre cesty dĺžky 11 a 12.
|
|---|