Structural aspects of graph coloring

Abstract

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

V 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