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*

Contact me at malcin at mimuw edu pl.