White Rose University Consortium logo
University of Leeds logo University of Sheffield logo York University logo

On hereditary graph classes defined by forbidding Truemper configurations: recognition and combinatorial optimization algorithms, and χ-boundedness results

Boncompagni, Valerio (2018) On hereditary graph classes defined by forbidding Truemper configurations: recognition and combinatorial optimization algorithms, and χ-boundedness results. PhD thesis, University of Leeds.

[img]
Preview
Text
main.pdf - Final eThesis - complete (pdf)
Available under License Creative Commons Attribution-Noncommercial-Share Alike 2.0 UK: England & Wales.

Download (1194Kb) | Preview

Abstract

Truemper configurations are four types of graphs that helped us understand the structure of several well-known hereditary graph classes. The most famous examples are perhaps the class of perfect graphs and the class of even-hole-free graphs: for both of them, some Truemper configurations are excluded (as induced subgraphs), and this fact appeared to be useful, and played some role in the proof of the known decomposition theorems for these classes. The main goal of this thesis is to contribute to the systematic exploration of hereditary graph classes defined by forbidding Truemper configurations. We study many of these classes, and we investigate their structure by applying the decomposition method. We then use our structural results to analyze the complexity of the maximum clique, maximum stable set and optimal coloring problems restricted to these classes. Finally, we provide polynomial-time recognition algorithms for all of these classes, and we obtain χ-boundedness results.

Item Type: Thesis (PhD)
Keywords: structural graph theory, graph algorithms, combinatorial optimization
Academic Units: The University of Leeds > Faculty of Engineering (Leeds) > School of Computing (Leeds)
Depositing User: Valerio Boncompagni
Date Deposited: 01 Apr 2019 08:47
Last Modified: 01 Apr 2019 08:47
URI: http://etheses.whiterose.ac.uk/id/eprint/23386

You do not need to contact us to get a copy of this thesis. Please use the 'Download' link(s) above to get a copy.
You can contact us about this thesis. If you need to make a general enquiry, please see the Contact us page.

Actions (repository staff only: login required)