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

The call for PhD positions starting in October 2023 has finished. The stipend committee has decided to offer the positions to Jadwiga Czyzewska and Kacper Kluk, and evaluated all other applicants as not sufficiently qualified for the positions.