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.
A definitely not exhaustive list of existing work relevant to the project.
All known algorithms in this section are based on (some variant of) Potential Maximal Cliques.
We organize Structural Graph Theory Bootcamp 22-26.09 in Warsaw.
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.