Název:
Varianty problému obarvení
Překlad názvu:
Graph coloring problems
Autoři:
Lidický, Bernard ; Fiala, Jiří (vedoucí práce) ; Paulusma, Daniel (oponent) ; Šámal, Robert (oponent) Typ dokumentu: Disertační práce
Rok:
2011
Jazyk:
eng
Abstrakt: [eng][cze] 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 cyclesNá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
Klíčová slova:
kritické grafy; krátké cykly; rovinné grafy; seznamové barvení; vlnové barvení; critical graphs; list coloring; packing coloring; planar graphs; short cycles