Original title:
Barevnost grafů na plochách
Translated title:
Barevnost grafů na plochách
Authors:
Tůma, Vojtěch ; Dvořák, Zdeněk (advisor) ; Fiala, Jiří (referee) Document type: Bachelor's theses
Year:
2011
Language:
eng Abstract:
[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
Keywords:
coloring; graph; surfaces
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/50264