Thesis (Selection of subject)Thesis (Selection of subject)(version: 368)
Thesis details
   Login via CAS
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.
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.
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).
Charles University | Information system of Charles University |