Original title:
Paritní vrcholová barvení
Translated title:
Parity vertex colorings
Authors:
Soukup, Jan ; Gregor, Petr (advisor) ; Kučera, Petr (referee) Document type: Bachelor's theses
Year:
2018
Language:
eng Abstract:
[eng][cze] A parity path in a vertex colouring of a graph G is a path in which every colour is used even number of times. A parity vertex colouring is a vertex colouring having no parity path. Let χp(G) be the minimal number of colours in a parity vertex colouring of G. It is known that χp(Bn) ≥ √ n where Bn is the complete binary tree with n layers. We show that the sharp inequality holds. We use this result to obtain a new bound χp(T) > 3 √ log n where T is any binary tree with n vertices. We study the complexity of computing the parity chromatic number χp(G). We show that checking whether a vertex colouring is a parity vertex colouring is coNP-complete and we design an exponential algorithm to com- pute it. Then we use Courcelle's theorem to prove the existence of a FPT algorithm checking whether χp(G) ≤ k parametrized by k and the treewidth of G. Moreover, we design our own FPT algorithm solving the problem. This algorithm runs in polynomial time whenever k and the treewidth of G is bounded. Finally, we discuss the relation of this colouring to other types of colourings, specifically unique maximum, conflict free, and parity edge colourings.Paritní cesta ve vrcholovém barvení grafu G je cesta ve které je každá barva použita sudě-krát. Paritní vrcholové barvení je barvení, které nemá žádnou paritní cestu. Nechť χp(G) je minimální počet barev v paritním bar- vení grafu G. Je známo, že χp(Bn) ≥ √ n, kde Bn je úplný binární strom s n vrstvami. Dokážeme, že platí ostrá nerovnost, a pomocí tohoto odhadu dokážeme nový odhad χp(T) > 3 √ log n, kde T je libovolný binární strom s n vrcholy. Dále se zabýváme časovou složitostí výpočtu paritního chromatického čísla χp(G). Dokážeme, že ověřování korektnosti paritního vrcholového bar- vení je coNP-úplné a popíšeme exponenciální algoritmus, který ho počítá. Dále pomocí Courcelleho věty dokážeme že existuje FPT algoritmus parame- trizovaný počtem barev k a stromovou šířkou grafu G ověřující že χp(G) ≤ k. Navíc popíšeme náš vlastní FPT algoritmus řešící tento problém. Tento al- goritmus běží v polynomiálním čase pro omezené k a stromovou šířku G. Na- konec zkoumáme příbuznost tohoto barvení s dalšími barveními, konkrétně s unique maximum, conflict free a parity edge barveními.
Keywords:
binary tree; conflict free colouring; FPT; parity vertex colouring; treewidth; unique maximum colouring; binární strom; conflict free colouring; FPT; paritní vrcholové barvení; stromová šířka; unique maximum colouring
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/99787