Home > Search Results: Esperet, Louis
Search:
Search Tips :: Advanced Search
Search collections:
Sort by: Display results: Output format:
National Repository of Grey Literature 1 records found  Search took 0.00 seconds. 
Structural aspects of graph coloring
 Pekárek, Jakub ; Dvořák, Zdeněk (advisor) ; Esperet, Louis (referee) ; Zhu, Xuding (referee)
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
Detailed record

Interested in being notified about new results for this query?
Subscribe to the RSS feed.
Digital Repository :: Search :: Submit :: Personalize :: Help
Powered by Invenio v1.1.2
Maintained by admin.invenio@techlib.cz
This site is also available in the following languages:
Česky  English