Back to search

University of Leeds

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

Abstract

dc:description.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.

Degree

thesis:*
Name dc:type.qualificationname
Ph.D
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Leeds
Year dc:date.issued
2018

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Boncompagni, Valerio
Advisors dc:contributor.advisor
  • Vuskovic, Kristina
  • Dyer, Martin

Rights

Language dc:language.dcterms_iso639_2
eng

Identifiers

dc:identifier.*
Identifier
uk.bl.ethos.770096

Chain of custody

source
Harvested from
White Rose University Consortium
Base URL
etheses.whiterose.ac.uk/cgi/oai2
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

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