Barvení grafů za použití nikdenenulových toků
| Thesis title in Czech: | Barvení grafů za použití nikdenenulových toků |
|---|---|
| Thesis title in English: | Graph coloring via nowhere-zero flows |
| Academic year of topic announcement: | 2018/2019 |
| Thesis type: | project |
| Thesis language: | |
| Department: | Computer Science Institute of Charles University (32-IUUK) |
| Supervisor: | prof. Mgr. Zdeněk Dvořák, Ph.D. |
| Author: | hidden - assigned by the advisor |
| Date of registration: | 14.11.2018 |
| Date of assignment: | 14.11.2018 |
| Guidelines |
| Dualitu mezi barvením a nikdenenulovými toky lze použít k návrhu algoritmů pro 3-barevnost rovinných grafů či grafů vnořených na jiné plochy omezeného rodu; viz například Dvořák a Lidický [DL]. Tento algoritmus je teoreticky efektivní v případě, že skoro všechny stěny uvažovaného grafu mají délku 4.
Cílem práce je implementovat takový algoritmus (alespoň pro rovinné grafy, případně např. pro projektivně rovinné grafy či grafy na toru) a vyhodnotit jeho efektivitu např. ve srovnání s optimalizovaným backtrackingem či algoritmem využívajícím existenci malých separátorů na vhodných třídách grafů (náhodné rovinné grafy dané hustoty, či grafy z nějakého benchmarku). Výsledky práce budou prezentovány formou zaslání na SVOČ. |
| References |
| [DL] Zdeněk Dvořák, Bernard Lidický: 3-Coloring Triangle-Free Planar Graphs with a Precolored 8-Cycle. Journal of Graph Theory 80(2): 98-111 (2015)
[BT] Mohar, Bojan, and Carsten Thomassen. Graphs on surfaces. Vol. 10. JHU Press, 2001. |