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.