Structural aspects of graph coloring
| Název práce v češtině: | Strukturální aspekty grafové barevnosti |
|---|---|
| Název v anglickém jazyce: | Structural aspects of graph coloring |
| Klíčová slova: | teorie grafů|barvení|torus|algoritmy|induced odd cycle packing number |
| Klíčová slova anglicky: | graph theory|coloring|torus|algorithms|induced odd cycle packing number |
| Akademický rok vypsání: | 2017/2018 |
| Typ práce: | disertační práce |
| Jazyk práce: | angličtina |
| Ústav: | Informatický ústav Univerzity Karlovy (32-IUUK) |
| Vedoucí / školitel: | prof. Mgr. Zdeněk Dvořák, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 22.09.2017 |
| Datum zadání: | 22.09.2017 |
| Datum potvrzení stud. oddělením: | 03.10.2017 |
| Datum a čas obhajoby: | 09.05.2023 09:00 |
| Datum odevzdání elektronické podoby: | 13.12.2022 |
| Datum odevzdání tištěné podoby: | 02.01.2023 |
| Datum proběhlé obhajoby: | 09.05.2023 |
| Oponenti: | Louis Esperet |
| prof. Xuding Zhu | |
| Zásady pro vypracování |
| 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. |
| Seznam odborné literatury |
| 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). |