Structural aspects of graph coloring
Strukturální aspekty grafové barevnosti
dissertation thesis (DEFENDED)
View/ Open
Permanent link
http://hdl.handle.net/20.500.11956/184183Identifiers
Study Information System: 190005
Collections
- Kvalifikační práce [10932]
Author
Advisor
Referee
Esperet, Louis
Zhu, Xuding
Faculty / Institute
Faculty of Mathematics and Physics
Discipline
Computer Science - Theory of Computing, Discrete Models and Optimization
Department
Computer Science Institute of Charles University
Date of defense
9. 5. 2023
Publisher
Univerzita Karlova, Matematicko-fyzikální fakultaLanguage
English
Grade
Pass
Keywords (Czech)
teorie grafů|barvení|torus|algoritmy|induced odd cycle packing numberKeywords (English)
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