|
|
Grid representations of graphs and the chromatic number
Balko, Martin ; Valtr, Pavel (vedoucí práce) ; Kratochvíl, Jan (oponent)
Mřížková nakreslení grafů a chromatické číslo Martin Balko 1. srpna 2012 Katedra (ústav): Katedra aplikované matematiky Vedoucí diplomové práce: doc. RNDr. Pavel Valtr Dr. e-mail vedoucího: valtr@kam.mff.cuni.cz Abstrakt V předložené práci se zabýváme mřížkovými nakresleními grafů a jejich souvislostmi s grafovými obarveními. Mřížkové nakreslení grafu zobrazuje vrcholy na body mřížky Zd a hrany na úsečky, které se vyhýbají bodům odpovídajícím nekoncovým vrcholům. Nejdříve dokážeme, že graf je qd - obarvitelný, d, q ≥ 2, právě tehdy, když má mřížkové nakreslení, ve kterém každá úsečka protíná nanejvýš q mřížkových bodů. Poté se věnujeme mřížkovým nakreslením s omezeným počtem sloupců, kde představíme nové NP-úplné úlohy a rozšíříme některé známé výsledky. Také ukážeme ostrý dolní odhad na plochu mřížkového nakreslení pro úplné vyvážené k-partitní grafy, čímž dokážeme domněnku D. R. Wooda. Nakonec pro libovolný rovinný graf nalezneme rovinné mřížkové nakreslení, kde každá úsečka obsahuje pouze dva mřížkové body. Tím potvrdíme domněnky od autorů D. Flores Pe˝nalozy a F. J. Zaragoza Martineze. Klíčová slova: mřížková nakreslení, mřížka, chromatické číslo, rovina
|
host ::
RSS.