Original title:
Varianty problému obarvení
Translated title:
Varianty problému obarvení
Authors:
Lidický, Bernard ; Kráľ, Daniel (referee) ; Fiala, Jiří (advisor) Document type: Master’s theses
Year:
2007
Language:
eng Abstract:
[eng][cze] The choice number is a graph parameter that generalizes the chromatic number. In this concept vertices are assigned lists of available colors. A graph is k-choosable if it can be colored whenever the lists are of size at least k. It is known that every planar graph without triangles is 4-choosable and there is an example of a non-3-choosable planar graph without triangles. In this work we study the choice number of planar graph without triangles and other short cycles.V předložené práci studujeme seznamové barvení rovinných grafů. Seznamové barvení je varianta problému barvení grafu, kde každý vrchol má přidělený svůj vlastní seznam možných barev. Říkáme, že graf je k-vybíravý, je-li možnée nalézt dobré obarvení pokaždé, když všechny seznamy obsahují alespoň k barev. Je známo, že každý rovinný graf bez trojúhelníků je 4-vybíravý a každý rovinný bipartitní graf (t.j. bez lichých cyklů) je 3-vybíravý. Práce ukazuje postačující podmínky pro 3-vybíravost rovinných grafů bez trojúhelníků s omezeným výskytem krátkých cyklů.
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/13262