Structural aspects of graph coloring
Strukturální aspekty grafové barevnosti
dizertační práce (OBHÁJENO)
Zobrazit/ otevřít
Trvalý odkaz
http://hdl.handle.net/20.500.11956/184183Identifikátory
SIS: 190005
Kolekce
- Kvalifikační práce [10932]
Autor
Vedoucí práce
Oponent práce
Esperet, Louis
Zhu, Xuding
Fakulta / součást
Matematicko-fyzikální fakulta
Obor
Informatika - teorie, diskrétní modely a optimalizace
Katedra / ústav / klinika
Informatický ústav Univerzity Karlovy
Datum obhajoby
9. 5. 2023
Nakladatel
Univerzita Karlova, Matematicko-fyzikální fakultaJazyk
Angličtina
Známka
Prospěl/a
Klíčová slova (česky)
teorie grafů|barvení|torus|algoritmy|induced odd cycle packing numberKlíčová slova (anglicky)
graph theory|coloring|torus|algorithms|induced odd cycle packing numberV této práci studujeme strukturální aspekty a algoritmické vlastnosti grafů vnořených nebo reprezentovaných v plochách a s omezeními na jejich stěny nebo cykly. Nejprve navrhneme způsob kvantifikace vlastností toků vnořených v ploše a jeho ap- likací získáváme algoritmus rozhodující rozšířitelnost předbarvení grafů skoro-kvadrangulujících válec, s předbarvenou hranicí válce. Následně vyvineme metodu redukce problému 3- obarvitelnosti grafů vnořených v toru bez trojúhelníků na problém 3-obarvitelnosti skoro- kvadrangulací toru. Získáme praktický algoritmus pro rozhodování 3-obarvitelosti v lineárním čase a pro nalezení 3-barvení v kvadratickém čase. V druhé části zkoumáme vztahy mezi geometrickými reprezentacemi grafů a parame- trem maximální velikost indukovaného pakování lichých cyklů (zkráceně iocp, induced odd cycle packing number). Ukážeme, že v celé řadě tříd geometricky reprezentovatelných grafů je tento parametr omezený, a že tyto třídy jsou χ-omezené (χ-bounded). Na zák- ladě těchto pozorování navrhneme EPTAS pro řešení problému velikosti největší nezávislé množiny pro grafy s omezeným iocp a lineární velikostí vejvětší nezávislé množiny, a také QPTAS pro stejný problém předpokládající pouze omezenost iocp parametru. 1
In this thesis, we study the structural and algorithmic properties of graphs embedded or represented in surfaces and with constraints on their faces or cycles. We derive tools to quantify properties of embedded flows and use these to design an algorithm to decide the extendability of a precoloring of the boundary cycles of near- quadrangulations of the cylinder. We then develop methods to reduce 3-coloring of triangle- free graphs embedded in the torus to 3-coloring near-quadrangulations, obtaining prac- tical algorithms for deciding 3-colorability in linear time, and obtaining a 3-coloring in quadratic time. We also investigate connection between geometric graph representations and the in- duced odd cycle packing number (iocp) parameter. We show that wide variety of rep- resentable graphs exhibit limited iocp and show that graphs with limited iocp are χ- bounded. We derive an EPTAS for maximum independent set of graphs with limited iocp and linear independence number, as well as QPTAS assuming only limited iocp. 1