Parity vertex colorings

• Název práce v češtině: Paritní vrcholová barvení
• Název v anglickém jazyce: Parity vertex colorings
• Klíčová slova: paritní vrcholové barvení, conflict free colouring, unique maximum colouring, binární strom, stromová šířka, FPT
• Klíčová slova anglicky: parity vertex colouring, conflict free colouring, unique maximum colouring, binary tree, treewidth, FPT
• Akademický rok vypsání: 2017/2018
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Vedoucí / školitel: doc. Mgr. Petr Gregor, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 07.12.2017
• Datum zadání: 07.12.2017
• Datum potvrzení stud. oddělením: 31.01.2018
• Datum a čas obhajoby: 22.06.2018 10:00
• Datum odevzdání elektronické podoby: 15.05.2018
• Datum odevzdání tištěné podoby: 18.05.2018
• Datum proběhlé obhajoby: 22.06.2018
• Oponenti: RNDr. Petr Kučera, Ph.D.

Zásady pro vypracování

Barvení grafu G je paritní, pokud se na každé cestě v G vyskytuje nějaká barva v lichém počtu. Cílem práce je seznámit se výsledky o paritních vrcholových barveních grafů, studovat jejich vztah k příbuzným barvením, zabývat se souvisejícími algoritmickými otázkami a pokusit se vyřešit některé otevřené problémy pro tato barvení na vybraných třídách grafů.

Seznam odborné literatury

P. Borowiecki, K. Budajová, S. Jendrol' and S. Krajči, Parity vertex colouring of graphs, Discuss. Math. Graph Theory 31 (2011), 183-195.

D. P. Bunde, K. Milans, D. B. West and H. Wu, Parity and strong parity edge-colorings of graphs, Combinatorica 28 (2008), 625-632.

P. Gregor, R. Škrekovski, Parity vertex colorings of binomial trees, Discuss. Math. Graph Theory 32 (2012), 177-180.