Témata prací (Výběr práce)Témata prací (Výběr práce)(verze: 336)
Detail práce
  
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).
 
Univerzita Karlova | Informační systém UK