Seznamová barevnost - aktuální otázky
| Thesis title in Czech: | Seznamová barevnost - aktuální otázky |
|---|---|
| Thesis title in English: | New challenges in list coloring |
| Academic year of topic announcement: | 2023/2024 |
| Thesis type: | dissertation |
| Thesis language: | |
| Department: | Computer Science Institute of Charles University (32-IUUK) |
| Supervisor: | prof. Mgr. Zdeněk Dvořák, Ph.D. |
| Author: |
| Guidelines |
| Breakthroughs on the topic of list coloring (bounds on the sizes of critical graphs drawn on surfaces, resolution of Ohba's conjecture) achieved in the last decade open the possibility to resolve further fundamental questions in this area. The thesis focuses on obtaining detailed knowledge concerning list coloring of embedded graphs, density of graphs critical for list coloring, list coloring properties in classes with forbidden induced subgraphs, and other related topics. |
| References |
| Mohar, B. and Thomassen, C., 2001. Graphs on surfaces (Vol. 16). Baltimore: Johns Hopkins University Press.
Postle L, Thomas R. Hyperbolic families and coloring graphs on surfaces. Transactions of the American Mathematical Society, Series B 5 (2018), 167-221. Noel JA, West DB, Wu H, Zhu X. Beyond Ohba’s Conjecture: A bound on the choice number of k-chromatic graphs with n vertices. European Journal of Combinatorics 43 (2015), 295-305. Postle LJ. 5-list-coloring graphs on surfaces. PhD thesis, Georgia Institute of Technology (2012). |