Strukturální aspekty grafové barevnosti
| Název práce v češtině: | Strukturální aspekty grafové barevnosti |
|---|---|
| Název v anglickém jazyce: | Structural aspects of graph coloring |
| Akademický rok vypsání: | 2017/2018 |
| Typ práce: | disertační práce |
| Jazyk práce: | |
| Ú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 |
| 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). |