Structural and algorithmic properties of hereditary graph classes

  project SONATA BIS, running July 2024 to June 2029. PI:

Our research lies on the boundary of structural and algorithmic graph theory.
The starting point is the long-standing open problem of complexity of problems like Maximum Independent Set in graph classes like graphs excluding a fixed path or subdivided claw (three-leaf tree) as induced subgraphs. There is an accelerated progress in recent years here.
We are also interested in related purely graph-theoretical questions such as chi-boundedness and the Erdos-Hajnal property in these and related graph classes.

Exemplary Topics

Quasipolynomial-time algorithms

• QPTAS for Pt-free and Sttt-free graphs
• The clean n^O(log^2 n) algorithm for MIS in Pt-free graphs
• Earlier quasipolynomial-time algorithm of Peter and Daniel (more complicated)
• Generalizing to many problems (incl. Feedback Vertex Set) and C_{>t}-free graphs

Polynomial-time algorithms

• Classic Bouchitte-Todinca introducing the framework
• Modern dynamic programming with all MSO2 problems
• P5-free case
• P6-free case
• Containers (incl. simpler algorithm for the P5-free case)

Chi-boundedness

• Recent survey of Scott and Seymour
• Seymour's webpage with series of papers on Induced subgraphs of graphs with large chromatic number and Polynomial bounds for chromatic number

Erdos-Hajnal Conjecture

• Very recent exciting progress
• C5-free case
• Caterpillars
• Pt-free case
• Seymour's webpage with the series of papers on Pure pairs

Bootcamp

Positions