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.


Erdos-Hajnal Conjecture


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


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.

Contact me at malcin at mimuw edu pl.