Marcin Wrochna
m.wrochna
mimuw.edu.pl
My interests range over theoretical aspects of computer science,
focusing algorithmic graph theory, constraint satisfaction, and parameterized complexity.
Currently I am looking into connections to more applied algorithmics.
My PhD thesis investigated multiplicative graphs, which are the subject of Hedetniemi's conjecture (on coloring graph products), as well as spaces of graph homomorphisms, using new algebraic-topological methods.
Publications
[DBLP]
2020
2019
2018
2017
2016
- Tight lower bounds for the complexity of multicoloring
with Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk, Arkadiusz Socała
ESA 2017 | ACM Trans. Comput. Theory (TOCT) - Cutwidth: obstructions and algorithmic aspects
with Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos
IPEC 2016, Best Paper award | invited to Algorithmica special issue - Linear kernels for edge deletion problems to immersion-closed graph classes
with Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos
ICALP 2017 - Square-free graphs are multiplicative SIAM DM 2016 | J. Comb. Theory B (JCTB)
presentation | Young Author Prize at Bordeaux Graph Workshop
2015
2014
* pronounced [ˈmarʨ̑in 'vrɔxna], like "mar-chin vroh-na", but "Martin" is perfectly fine :)