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.

- 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

- 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)

- 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*

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

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.