| Název: | Chromatická teorie grafů |
| Další názvy: | Chromatic graph theory |
| Autoři: | Petříčková, Šárka |
| Vedoucí práce/školitel: | Kaiser, Tomáš |
| Datum vydání: | 2017 |
| Nakladatel: | Západočeská univerzita v Plzni |
| Typ dokumentu: | disertační práce |
| URI: | http://hdl.handle.net/11025/28547 |
| Klíčová slova: | barvení grafů;barevnost;ramseyove teorie;online barvení;nevyhnutelný graf;seznamová barevnost;totální barevnost;racionální mocniny grafů;herní barevnost |
| Klíčová slova v dalším jazyce: | graph coloring;ramsey theory;online coloring;unavoidable graph;chromatic number;list coloring;total coloring;fractional power;graph powers;game chromatic number;game coloring |
| Abstrakt: | Cílem této práce je studium několika problémů v oblasti barvení grafů. V úvodu nejprve ukážeme, že teorie barvení grafů nabízí užitečné nástroje pro modelování široké škály problémů z praxe. Dále seznámíme čtenáře se základní terminologií a stěžejními výsledky v oblasti chromatické teorie grafů. Hlavní část disertační práce je rozdělena do čtyř kapitol podle následujících témat: Online Ramseyova teorie, Barevnost racionálních mocnin grafů, Seznamová barevnost mocnin grafů, a Herní barevnost. V každé z těchto kapitol představíme daný problém, uvedeme známé a nové výsledky, a navrhneme několik otevřených problémů. Publikace výsledků prvních třech kapitol jsou přiloženy na konci práce. Výsledky uvedené a dokázané v poslední kapitole nebyly publikovány. |
| Abstrakt v dalším jazyce: | The goal of this thesis is to analyze several distinct problems regarding graph colorings. To motivate the topic, we first demonstrate that the theory of graph coloring provides useful tools for modeling a wide variety of scheduling and assignment problems. We then introduce basic notation and review fundamental results in the area of chromatic graph theory. The main part of the thesis is divided into four chapters devoted to the following topics: Online Ramsey theory, Chromatic number of fractional graph powers, List chromatic number of graph powers, and Game chromatic number. In each of these chapters we introduce the graph coloring problem, give an overview of known results, present new results, and state several open problems. The published/accepted papers for the first three problems are attached at the end of the thesis. The results stated and proved in the last chapter have not been published. |
| Práva: | Plný text práce je přístupný bez omezení. |
| Vyskytuje se v kolekcích: | Disertační práce / Dissertations (KMA) |
Soubory připojené k záznamu:
| Soubor | Popis | Velikost | Formát | |
|---|---|---|---|---|
| Petrickova_Disertace_CZabstract_publications.pdf | Plný text práce | 1,36 MB | Adobe PDF | Zobrazit/otevřít |
| posudky-odp-petrickova.pdf | Posudek oponenta práce | 1,95 MB | Adobe PDF | Zobrazit/otevřít |
| protokol-odp-petrickova.pdf | Průběh obhajoby práce | 819,56 kB | Adobe PDF | Zobrazit/otevřít |
Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam:
http://hdl.handle.net/11025/28547Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.