Structural and algorithmic properties of hereditary graph classes

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

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

A definitely not exhaustive list of existing work relevant to the project.

Quasipolynomial-time algorithms

Polynomial-time algorithms

All known algorithms in this section are based on (some variant of) Potential Maximal Cliques.

Chi-boundedness

Erdos-Hajnal Conjecture


Bootcamp

We organize Structural Graph Theory Bootcamp 22-26.09 in Warsaw.

Positions

There will be two PhD positions announced soon, starting in October 2023. The positions come with a stipend of 5000 PLN / month.
Contact me at malcin at mimuw edu pl.