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. 1 V 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

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/50264

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-314553


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce