Název:
Barevnost grafů na plochách
Překlad názvu:
Barevnost grafů na plochách
Autoři:
Tůma, Vojtěch ; Dvořák, Zdeněk (vedoucí práce) ; Fiala, Jiří (oponent) Typ dokumentu: Bakalářské práce
Rok:
2011
Jazyk:
eng
Abstrakt: [eng][cze] In this thesis we deal with extending a 4-coloring of a cycle into the rest of the graph. We prove that for plane 3-colorable graphs such that every face except the outer face O is a triangle and O has length 4 or 5, the question of extendability of a precoloring of O reduces to extendability into 3 small basic graphs. We also classify the situation when there is an inner face of size 5 in the graph in similar terms. 1V této práci se zabýváme rozšiřováním 4-obarvení cyklu do zbytku grafu. Ukážeme, že pro rovinný 3-barevný graf takový, že vnější stěna O má velikost 4 nebo 5 a všechny ostatní stěny mají velikost 3, se otázka rozšiřitelnosti předbarvení O redukuje na otázku rozšiřitelnosti předbarvení do 3 malých základních grafů. Dále podobným způsobem klasifikujeme i situaci, kdy je v grafu stěna velikosti 4 různá od O. 1
Klíčová slova:
coloring; graph; surfaces