Structural aspects of graph coloring
| Thesis title in Czech: | Strukturální aspekty grafové barevnosti |
|---|---|
| Thesis title in English: | Structural aspects of graph coloring |
| Key words: | teorie grafů|barvení|torus|algoritmy|induced odd cycle packing number |
| English key words: | graph theory|coloring|torus|algorithms|induced odd cycle packing number |
| Academic year of topic announcement: | 2017/2018 |
| Thesis type: | dissertation |
| Thesis language: | angličtina |
| Department: | Computer Science Institute of Charles University (32-IUUK) |
| Supervisor: | prof. Mgr. Zdeněk Dvořák, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 22.09.2017 |
| Date of assignment: | 22.09.2017 |
| Confirmed by Study dept. on: | 03.10.2017 |
| Date and time of defence: | 09.05.2023 09:00 |
| Date of electronic submission: | 13.12.2022 |
| Date of submission of printed version: | 02.01.2023 |
| Date of proceeded defence: | 09.05.2023 |
| Opponents: | Louis Esperet |
| prof. Xuding Zhu | |
| Guidelines |
| Jedním z důležitých nástrojů pro studium grafové barevnosti a vývoj algoritmů v této oblasti je popis struktury kritických grafů, které vynucují vysokou barevnost. Další intenzivně zkoumanou oblastí je studium barevnosti ve speciálních třídách dobře strukturovaných grafů, například bez nějakého zakázaného minoru. Cílem práce je dosažení nových výsledků v těchto a dalších souvisejících oblastech propojujících strukturální teorii grafů se studiem grafové barevnosti. |
| References |
| Luke Postle, Robin Thomas: Hyperbolic families and coloring graphs on surfaces, arXiv 1609.06749 (2016).
Alexandr V. Kostochka, Matthew Yancey: Ore's conjecture on color-critical graphs is almost true. J. Comb. Theory, Ser. B 109 (2014), 73-101. Naonori Kakimura, Ken-ichi Kawarabayashi: Coloring immersion-free graphs. J. Comb. Theory, Ser. B 121 (2016), 284-307. B. Mohar, C. Thomassen: Graphs on Surfaces, Johns Hopkins Press, Baltimore (2001). |