velikost textu

Graph coloring problems

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Graph coloring problems
Název v češtině:
Varianty problému obarvení
Typ:
Disertační práce
Autor:
RNDr. Bernard Lidický, Ph.D.
Školitel:
doc. RNDr. Jiří Fiala, Ph.D.
Oponenti:
Dr. Daniel Paulusma
Mgr. Robert Šámal, Ph.D.
Id práce:
44599
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra aplikované matematiky (32-KAM)
Program studia:
Informatika (P1801)
Obor studia:
Diskrétní modely a algoritmy (4I4)
Přidělovaný titul:
Ph.D.
Datum obhajoby:
26. 7. 2011
Výsledek obhajoby:
Prospěl/a
Jazyk práce:
Angličtina
Klíčová slova:
kritické grafy, seznamové barvení, vlnové barvení, rovinné grafy, krátké cykly
Klíčová slova v angličtině:
critical graphs, list coloring, packing coloring, planar graphs, short cycles
Abstrakt:
Název práce: Varianty problému obarvení Autor: Bernard Lidický Katedra: Katedra aplikované matematiky Vedoucí disertační práce: doc. RNDr. Jiří Fiala, Ph.D. Abstrakt: V této práci studujeme barvení grafů. Práce je rozdělena do tří částí, kde každá část se zabývá jinou variantou barvení. V první části se zabýváme 6-kritickými grafy na plochách a 6-kritickými grafy s malým počtem křížení. Hlavními výsledky jsou kompletní seznam 6-kritických grafů na Kleinově láhvi a 6-kritických grafů s křížícím číslem nejvýše čtyři. Druhá část je věnována vybíravosti rovinných grafů bez krátkých cyklů. Ukazu- jeme, že rovinné grafy bez 3-,7- a 8-cyklů jsou 3-vybíravé a že rovinné grafy bez trojúhelníků a s jistým omezením na 4-cykly jsou též 3-vybíravé. V poslední části se zaměřujeme na novější variantu barvení - vlnové barvení. Jde o koncept, který je motivovaný přiřazováním frekvencí a má zohlednit, že různé frekvence mají různý dosah. Zabýváme se pak zlepšováním odhadů nutného počtu barev k obarvení čtvercové a šestiúhelníkové mřížky. Klíčová slova: kritické grafy, seznamové barvení, vlnové barvení, rovinné grafy, krátké cykly
Abstract v angličtině:
Title: Graph coloring problems Author: Bernard Lidický Department: Department of Applied Mathematics Supervisor: doc. RNDr. Jiří Fiala, Ph.D. Abstract: As the title suggests, the central topic of this thesis is graph coloring. The thesis is divided into three parts where each part focuses on a different kind of coloring. The first part is about 6-critical graphs on surfaces and 6-critical graphs with small crossing number. We give a complete list of all 6-critical graphs on the Klein bottle and complete list of all 6-critical graphs with crossing number at most four. The second part is devoted to list coloring of planar graphs without short cycles. We give a proof that planar graphs without 3-,6-, and 7- cycles are 3-choosable and that planar graphs without triangles and some constraints on 4-cycles are also 3-choosable. In the last part, we focus on a recent concept called packing coloring. It is motivated by a frequency assignment problem where some frequencies must be used more sparsely that others. We improve bounds on the packing chromatic number of the infinite square and hexagonal lattices. Keywords: critical graphs, list coloring, packing coloring, planar graphs, short cycles
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce RNDr. Bernard Lidický, Ph.D. 1.05 MB
Stáhnout Příloha k práci RNDr. Bernard Lidický, Ph.D. 2.96 MB
Stáhnout Abstrakt v českém jazyce RNDr. Bernard Lidický, Ph.D. 36 kB
Stáhnout Abstrakt anglicky RNDr. Bernard Lidický, Ph.D. 37 kB
Stáhnout Posudek vedoucího doc. RNDr. Jiří Fiala, Ph.D. 79 kB
Stáhnout Posudek oponenta Dr. Daniel Paulusma 37 kB
Stáhnout Posudek oponenta Mgr. Robert Šámal, Ph.D. 80 kB
Stáhnout Záznam o průběhu obhajoby prof. RNDr. Jaroslav Nešetřil, DrSc. 62 kB