Parity vertex colorings
| Thesis title in Czech: | Paritní vrcholová barvení |
|---|---|
| Thesis title in English: | Parity vertex colorings |
| Key words: | paritní vrcholové barvení, conflict free colouring, unique maximum colouring, binární strom, stromová šířka, FPT |
| English key words: | parity vertex colouring, conflict free colouring, unique maximum colouring, binary tree, treewidth, FPT |
| Academic year of topic announcement: | 2017/2018 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | angličtina |
| Department: | Department of Theoretical Computer Science and Mathematical Logic (32-KTIML) |
| Supervisor: | doc. Mgr. Petr Gregor, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 07.12.2017 |
| Date of assignment: | 07.12.2017 |
| Confirmed by Study dept. on: | 31.01.2018 |
| Date and time of defence: | 22.06.2018 10:00 |
| Date of electronic submission: | 15.05.2018 |
| Date of submission of printed version: | 18.05.2018 |
| Date of proceeded defence: | 22.06.2018 |
| Opponents: | RNDr. Petr Kučera, Ph.D. |
| Guidelines |
| 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ů. |
| References |
| 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. |