My Research

I am Tomáš Masařík, an assistant professor at the Institute of Informatics, Faculty of Mathematics, Informatics and Mechanics, University of Warsaw.

My research interests include graph coloring, structural graph theory, algorithms, computational complexity, and parameterized complexity. You can also find my publications on Google Scholar and ORCID. My preprints are usually available on arXiv.

Previously, I was a postdoctoral fellow at Simon Fraser University, supervised by Bojan Mohar and Ladislav Stacho, and at the University of Warsaw, in the CUTACOMBS project, supervised by Marcin Pilipczuk, and the BOBR project, supervised by Michał Pilipczuk.

I obtained my PhD at the Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, in Prague, Czech Republic, under the supervision of Jiří Fiala. I was also affiliated with the Computer Science Institute of Charles University and participated in the Center of Excellence - Institute for Theoretical Computer Science.

Papers

1. Edge-Decomposition into Two Triangular Forests Is NP-Complete
   (Beniamin Bibrowski, TM)
   • arXiv.
2. Induced Erdős–Pósa Property for Long Holes, Long Thetas, and Beyond
   (Jadwiga Czyżewska, TM, Marcin Pilipczuk, Amadeus Reinald, Paweł Rzążewski)
   • arXiv.
3. PACE 2026 Solver Description: CherryPicker, a Heuristic Solver for the Maximum Agreement Forest Problem [PACE Challenge 2026, Heuristic and Lower-Bound Tracks]
   (Jakub Dziura, TM)
   • PDF.
   • GitHub.
4. Tree-Independence Number of P₅-Free Graphs with No Large Bicliques
   (Václav Blažej, J. Pascal Gollin, Tomáš Hons, TM, Martin Milanič, Paweł Rzążewski, Ondřej Suchý, Alexandra Wesolek)
   • ESA 2026 (proceedings).
   • arXiv.
5. QPTAS for MWIS and Finding Large Sparse Induced Subgraphs in Graphs with Few Independent Long Holes
   (Édouard Bonnet, Jadwiga Czyżewska, TM, Marcin Pilipczuk, Paweł Rzążewski)
   • SWAT 2026 (proceedings).
   • arXiv.
6. Optimal Path Partitions in Subcubic and Almost-Subcubic Graphs
   (TM, Michał Włodarczyk, Mehmet Akif Yıldız)
   • WG 2026 (proceedings).
   • arXiv.
7. Separator Theorem for Minor-Free Graphs in Linear Time
   (Édouard Bonnet, Tuukka Korhonen, Hung Le, Jason Li, TM)
   • STOC 2026 (proceedings).
   • arXiv.
   • Also presented at IBS Discrete Math Seminar 2026 (slides, recording).
8. Constricting the Computational Complexity Gap of the 4-Coloring Problem in (P_t, C₃)-Free Graphs
   (Justyna Jaworska, Bartłomiej Kielak, TM, Jana Masaříková)
   • arXiv.
   • Also presented at Cycles and Colourings 2025 (slides by Jana Masaříková).
9. General Strong Bound on the Uncrossed Number via a Tight Bound for the Maximum Uncrossed Subgraph Number
   (Gaspard Charvy, TM)
   • arXiv.
10. A Tight Meta-Theorem for LOCAL Certification of MSO₂ Properties within Bounded Treewidth Graphs
    (Linda Cook, Eun Jung Kim, TM)
    • PODC 2025 (proceedings).
    • arXiv.
11. Path Eccentricity and Forbidden Induced Subgraphs
    (Sylwia Cichacz, Claire Hilaire, TM, Jana Masaříková, Martin Milanič)
    • EUROCOMB 2025 (proceedings, slides).
    • arXiv.
12. Unbent Collections of Orthogonal Drawings
    (Todor Antić, Giuseppe Liotta, TM, Giacomo Ortali, Matthias Pfretzschner, Peter Stumpf, Alexander Wolff, Johannes Zink)
    • WG 2025 (proceedings; proceedings published in 2026).
    • arXiv.
13. Fair Vertex Problems Parameterized by Cluster Vertex Deletion
    (TM, Jędrzej Olkowski, Anna Zych-Pawlewicz)
    • arXiv.
14. On the Uncrossed Number of Graphs
    (Martin Balko, Petr Hliněný, TM, Joachim Orthaber, Birgit Vogtenhuber, Mirko H. Wagner)
    • GD 2024 (proceedings, slides).
    • arXiv.
    • Also presented at HOMONOLO 2024.
15. Finding Diverse Solutions Parameterized by Cliquewidth
    (Karolina Drabik, TM)
    • AAAI 2026 (proceedings).
    • arXiv.
16. Proper Rainbow Saturation Numbers for Cycles
    (Anastasia Halfpap, Bernard Lidický, TM)
    • Journal: Discrete Mathematics (2026).
    • EUROCOMB 2025 (proceedings, slides).
    • arXiv.
    • Also presented at Cycles and Colourings 2025 (slides).
17. Treewidth Is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor
    (Édouard Bonnet, Jędrzej Hodor, Tuukka Korhonen, TM)
    • arXiv.
18. A Generalised Theory of Proportionality in Collective Decision Making
    (TM, Grzegorz Pierczyński, Piotr Skowron)
    • Manuscript name: Group Fairness in Social Choice.
    • EC 2024 (proceedings).
    • arXiv.
    • Also presented at Warsaw–Krakow WKRECAI 2024 (slides).
19. Minimizing an Uncrossed Collection of Drawings
    (Petr Hliněný, TM)
    • GD 2023 (proceedings).
    • arXiv.
20. Maximum Weight Independent Set in Graphs with No Long Claws in Quasi-Polynomial Time
    (Peter Gartland, Daniel Lokshtanov, TM, Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski)
    • STOC 2024 (proceedings, recording (25 min), recording (35 min, MKV), slides).
    • arXiv.
    • Also presented at HALG 2024 (poster).
21. Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs Is Logarithmic
    (Jesse Campion Loth, Kevin Halasz, TM, Bojan Mohar, Robert Šámal)
    • SODA 2024 (proceedings, slides).
    • arXiv.
22. Proving a Directed Analog of the Gyárfás-Sumner Conjecture for Orientations of P₄
    (Linda Cook, TM, Marcin Pilipczuk, Amadeus Reinald, Uéverton S. Souza)
    • Journal: The Electronic Journal of Combinatorics (2023).
    • EUROCOMB 2023 (extended abstract).
    • arXiv.
    • Also presented at Dagstuhl Seminar 22481 (2022) (slides) and at the 10th Polish Combinatorial Conference (2024).
23. On Weighted Graph Separation Problems and Flow Augmentation
    (Eun Jung Kim, TM, Marcin Pilipczuk, Roohani Sharma, Magnus Wahlström)
    • Journal: SIAM Journal on Discrete Mathematics (2024).
    • arXiv.
24. A Tight Quasi-Polynomial Bound for Global Label Min-Cut
    (Lars Jaffke, Paloma T. Lima, TM, Marcin Pilipczuk, Uéverton S. Souza)
    • Journal: ACM Transactions on Algorithms (2026).
    • SODA 2023 (proceedings).
    • arXiv.
25. Fixed-Parameter Tractability of Directed Multicut with Three Terminal Pairs Parameterized by the Size of the Cutset: Twin-Width Meets Flow-Augmentation
    (Meike Hatzel, Lars Jaffke, Paloma T. Lima, TM, Marcin Pilipczuk, Roohani Sharma, Manuel Sorge)
    • SODA 2023 (proceedings).
    • arXiv.
26. Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument
    (Konrad Majewski, TM, Jana Masaříková, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, Marek Sokołowski)
    • Journal: ACM Transactions on Computation Theory (2024).
    • ICALP 2022 (proceedings).
    • arXiv.
    • Also presented at UW seminar & HU Berlin 2022 (slides).
27. List Locally Surjective Homomorphisms in Hereditary Graph Classes
    (Pavel Dvořák, Monika Krawczyk, TM, Jana Novotná, Paweł Rzążewski, Aneta Żuk)
    • ISAAC 2022 (proceedings).
    • arXiv.
28. Single-Conflict Colorings of Degenerate Graphs
    (Peter Bradshaw, TM)
    • Journal: Journal of Graph Theory (2025).
    • arXiv.
    • Also presented at Shanghai seminar 2021 (slides, recording (60 min)) and at EUROCOMB 2023 (abstract).
29. Linear Bounds for Cycle-Free Saturation Games
    (Sean English, TM, Grace McCourt, Erin Meger, Michael S. Ross, Sam Spiro)
    • Journal: The Electronic Journal of Combinatorics (2022).
    • arXiv.
    • Also presented at Cycles and Colourings 2023 (slides).
30. Tuza's Conjecture for Threshold Graphs
    (Marthe Bonamy, Łukasz Bożyk, Andrzej Grzesik, Meike Hatzel, TM, Jana Novotná, Karolina Okrasa)
    • Journal: Discrete Mathematics & Theoretical Computer Science (2022).
    • EUROCOMB 2021 (proceedings, slides).
    • arXiv.
31. Robust Connectivity of Graphs on Surfaces
    (Peter Bradshaw, TM, Jana Novotná, Ladislav Stacho)
    • Journal: SIAM Journal on Discrete Mathematics (2022).
    • EUROCOMB 2021 (proceedings, slides).
    • arXiv.
    • Also presented at CSGT 2022 (slides).
32. Constant Congestion Brambles in Directed Graphs
    (TM, Marcin Pilipczuk, Paweł Rzążewski, Manuel Sorge)
    • Journal: SIAM Journal on Discrete Mathematics (2022).
    • EUROCOMB 2021 (proceedings, slides).
    • arXiv.
    • Also presented at TU Berlin seminar 2021 (slides).
33. Random 2-Cell Embeddings of Multistars
    (Jesse Campion Loth, Kevin Halasz, TM, Bojan Mohar, Robert Šámal)
    • Journal: Proceedings of the AMS (2022).
    • EUROCOMB 2021 (proceedings).
    • arXiv.
34. The Phase Transition of Discrepancy in Random Hypergraphs
    (Calum MacRury, TM, Leilani Pai, Xavier Pérez-Giménez)
    • Journal: SIAM Journal on Discrete Mathematics (2023).
    • arXiv.
35. On 3-Coloring of (2P₄, C₅)-Free Graphs
    (Vít Jelínek, Tereza Klimošová, TM, Jana Novotná, Aneta Pokorná)
    • Journal: Algorithmica (2022).
    • WG 2021 (proceedings, slides, recording (25 min)).
    • arXiv.
36. On Weak Flexibility in Planar Graphs
    (Bernard Lidický, TM, Kyle Murphy, Shira Zerbib)
    • Journal: Graphs and Combinatorics (2022).
    • arXiv.
37. Flexible List Colorings in Graphs with Special Degeneracy Conditions
    (Peter Bradshaw, TM, Ladislav Stacho)
    • Journal: Journal of Graph Theory (2022).
    • ISAAC 2020 (proceedings).
    • arXiv.
    • Also presented at SIAM DM 2021, SFU Discrete Math 2021 (recording (50 min)), and UW algorithms seminar 2021 (slides, recording (50 min)).
38. Clique-Width: Harnessing the Power of Atoms
    (Konrad Dabrowski, TM, Jana Novotná, Daniël Paulusma, Paweł Rzążewski)
    • Journal: Journal of Graph Theory (2023).
    • WG 2020 (proceedings).
    • arXiv.
    • Also presented at Haifa workshop 2020 (slides).
39. Flexibility of Planar Graphs—Sharpening the Tools to Get Lists of Size Four
    (Ilkyoo Choi, Felix C. Clemen, Michael Ferrara, Paul Horn, Fuhong Ma, TM)
    • Journal: Discrete Applied Mathematics (2022).
    • arXiv.
    • Also presented at JMM 2020 (slides).
40. Optimal Discretization Is Fixed-Parameter Tractable
    (Stefan Kratsch, TM, Irene Muzi, Marcin Pilipczuk, Manuel Sorge)
    • SODA 2021 (proceedings).
    • arXiv.
    • Also presented at SFU Discrete Math 2021 (slides, recording (50 min)); Frontiers of Parameterized Complexity (recording (70 min)).
41. 𝒰-Bubble Model for Mixed Unit Interval Graphs and Its Applications: The MaxCut Problem Revisited
    (Jan Kratochvíl, TM, Jana Novotná)
    • Journal: Algorithmica (2021).
    • MFCS 2020 (proceedings; recording (20 min)).
    • arXiv.
42. Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View
    (Radek Hušek, Dušan Knop, TM)
    • IPEC 2020 (proceedings; recording (20 min, MKV)).
    • arXiv.
43. Jones' Conjecture in Subcubic Graphs
    (Marthe Bonamy, François Dross, TM, Andrea Munaro, Wojciech Nadara, Marcin Pilipczuk, Michał Pilipczuk)
    • Journal: The Electronic Journal of Combinatorics (2021).
    • arXiv.
44. FPT Algorithms for Diverse Collections of Hitting Sets
    (Julien Baste, Lars Jaffke, TM, Geevarghese Philip, Günter Rote)
    • Journal: Algorithms (2019; special issue).
    • arXiv.
45. Packing Directed Cycles Quarter- and Half-Integrally
    (TM, Irene Muzi, Marcin Pilipczuk, Paweł Rzążewski, Manuel Sorge)
    • Journal: Combinatorica (2022).
    • ESA 2019 (proceedings; slides).
    • arXiv.
    • Also presented at Cycles and Colourings 2019 and Iowa State (2020, recording (35 min)).
46. Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory
    (Julien Baste, Michael R. Fellows, Lars Jaffke, TM, Mateus de Oliveira Oliveira, Geevarghese Philip, Frances A. Rosamond)
    • Journal: Artificial Intelligence (2022).
    • IJCAI 2020 (proceedings; recording (5 min, MP4), recording (15 min), poster).
    • arXiv.
47. Flexibility of Planar Graphs Without 4-Cycles
    (TM)
    • EUROCOMB 2019 (proceedings article, slides).
    • arXiv.
    • PDF.
    • Also presented at DIMEA days 2019 (poster).
48. Flexibility of Planar Graphs of Girth at Least Six
    (Zdeněk Dvořák, TM, Jan Musílek, Ondřej Pangrác)
    • Journal: Journal of Graph Theory (2020).
    • arXiv.
    • PDF.
    • Also presented at DIMEA days 2019 (poster).
49. Flexibility of Triangle-Free Planar Graphs
    (Zdeněk Dvořák, TM, Jan Musílek, Ondřej Pangrác)
    • Journal: Journal of Graph Theory (2021).
    • arXiv.
    • Also presented at Cycles and Colourings 2017 (slides) and DIMEA days 2019 (poster).
50. Steiner Tree Heuristics [PACE Challenge 2018, Track C]
    (Radek Hušek, Tomáš Toufar, Dušan Knop, TM, Eduard Eiben)
    • PDF.
    • PACE report 2018.
    • IPEC ceremony results: 4th place.
    • Public repository.
    • Ranking on public instances.
51. Colouring (P_r+P_s)-Free Graphs
    (Tereza Klimošová, Josef Malík, TM, Jana Novotná, Daniël Paulusma, Veronika Slívová)
    • Journal: Algorithmica (2020).
    • ISAAC 2018 (proceedings; slides).
    • arXiv.
    • Also presented at ALGO seminar (Bergen, 2018, slides); Noon lecture (Charles University, 2018, slides).
52. Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
    (Pavel Dvořák, Andreas E. Feldmann, Dušan Knop, TM, Tomáš Toufar, Pavel Veselý)
    • Journal: SIAM Journal on Discrete Mathematics (2021).
    • STACS 2018 (proceedings; slides).
    • arXiv.
    • Also presented at PAAW 2018 (slides); HALG 2018 (poster).
53. On Difference Graphs and the Local Dimension of Posets
    (Jinha Kim, Ryan R. Martin, TM, Warren Shull, Heather C. Smith, Andrew Uzzell, Zhiyu Wang)
    • Journal: European Journal of Combinatorics (2020).
    • arXiv.
    • Also presented at Noon lecture (Prague, 2018) and ALGO seminar (Bergen, 2018, slides); HOMONOLO 2017.
54. Notes on Complexity of Packing Coloring
    (Minki Kim, Bernard Lidický, TM, Florian Pfender)
    • Journal: Information Processing Letters (2018).
    • arXiv.
    • Also presented at Warsaw University of Technology seminar; Cycles and Colourings 2018 (slides).
55. Duality Gap in Interval Linear Programming
    (Jana Novotná, Milan Hladík, TM)
    • Journal: Journal of Optimization Theory and Applications (2020).
    • SOR 2017 (proceedings; slides).
    • arXiv.
56. Parameterized Complexity of Fair Vertex Evaluation Problems
    (Dušan Knop, TM, Tomáš Toufar)
    • MFCS 2019 (proceedings; slides).
    • arXiv.
    • PDF.
    • Also presented at CSGT 2017 (slides); MCGTC 2017; GROW 2017 (slides); ISAAC 2018 open problems (slides).
57. Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity
    (Dušan Knop, Martin Koutecký, TM, Tomáš Toufar)
    • Journal: Logical Methods in Computer Science (2019).
    • WG 2017 (proceedings; slides).
    • arXiv.
    • Also presented at MCW XXII (2017).
58. Parameterized Complexity of Fair Deletion Problems
    (TM, Tomáš Toufar)
    • Journal: Discrete Applied Mathematics (2020).
    • TAMC 2017 (proceedings; slides).
    • arXiv.
    • Also presented at BGW 2016 (slides); MEMICS 2016 (poster).
59. Anti-Path Cover on Sparse Graph Classes
    (Pavel Dvořák, Dušan Knop, TM)
    • MEMICS 2016 (proceedings; slides).
    • arXiv.
    • Also presented at BGW 2016 (slides).
60. Triangle-Free Planar Graphs with the Smallest Independence Number
    (Zdeněk Dvořák, TM, Jan Musílek, Ondřej Pangrác)
    • Journal: Journal of Graph Theory (2019).
    • arXiv.
    • Also presented at Cycles and Colourings 2016 (slides).
61. Computational Complexity of Distance Edge Labeling
    (Dušan Knop, TM)
    • Journal: Discrete Applied Mathematics (2018).
    • IWOCA 2015 (proceedings; slides).
    • arXiv.
    • A pre-printed ITI-series version. Diploma Thesis (2014, CZ).
    • Also presented at Noon lecture (Prague, 2015).

Internships / Research Collaboration

• IBS, Daejeon, South Korea, Jan 2026 (E. J. Kim).
• CIMAT, Guanajuato, Mexico, Nov 2025 (Crossing Numbers Workshop 2025).
• University of Warsaw, Poland, Oct 2025 (AlgUW at Będlewo).
• University of Primorska, Koper, Slovenia, Aug 2024 (M. Milanič).
• University of Warsaw, Poland, Jul 2024 (Structural Graph Theory Workshop STWOR 2 at Chęciny).
• Simon Fraser University, Burnaby, BC, Canada, Jun 2024 (L. Stacho).
• Iowa State University, Ames, USA, Jan 2024 (B. Lidický).
• University of Warsaw, Poland, Sep 2023 (Structural Graph Theory Workshop STWOR at Będlewo).
• University of Maribor and University of Ljubljana, Slovenia, Jul 2023 (Crossing Numbers Workshop 2023).
• IT University of Copenhagen, Denmark, May 2023 (P. Lima).
• Leibniz-Zentrum für Informatik, Germany, Nov 2022 (Dagstuhl Seminar 22481).
• Masaryk University, Brno, Czech Republic, Oct 2022 (P. Hliněný).
• University of Warsaw, Poland, Jun 2022 (Structural Graph Theory Workshop at Gułtowy).
• Humboldt University of Berlin, Germany, Apr–Jun 2022 (S. Kratsch).
• University of Warsaw, Poland, Apr 2022 (Parameterized Algorithms Retreat of University of Warsaw).
• Jagiellonian University, Kraków, Poland, Dec 2021 (A. Grzesik).
• Charles University, Czech Republic, Sep 2021 (KAMAK).
• Postdoctoral fellow, University of Warsaw, Poland, Aug 2021–Feb 2022 (Michał Pilipczuk, project BOBR).
• Postdoctoral fellow, Simon Fraser University, Canada, Feb 2020–Aug 2021 (B. Mohar and L. Stacho).
• Iowa State University, USA, Jan 2020 (B. Lidický).
• Postdoctoral fellow, University of Warsaw, Poland, Oct 2019–Jan 2020 (Marcin Pilipczuk, project CUTACOMBS).
• Charles University, Czech Republic, Sep 2019 (KAMAK).
• Kansas University, USA, Jul 2019 (GRWC).
• Leibniz-Zentrum für Informatik, Germany, Jul 2019 (Dagstuhl Seminar 19271).
• Durham University, UK, Nov 2018, Apr–May 2019 (D. Paulusma).
• University of Warsaw, Poland, Feb 2019 (Parameterized Algorithms Retreat of University of Warsaw).
• Warsaw University of Technology, Poland, Nov 2018 (P. Rzążewski).
• University of Warsaw, Poland, Sep 2018–Sep 2019 (Marcin Pilipczuk, project CUTACOMBS).
• University of Bergen, Norway, Jan–Jul 2018 (Erasmus).
• LAMSADE, Université Paris-Dauphine, France, Dec 2017 (M. Lampis).
• Charles University, Czech Republic, Sep 2017 (KAMAK).
• University of Denver, Colorado and University of Colorado Denver, USA, Jul 2017 (GRWC).
• Charles University, Czech Republic, Sep 2016 (KAMAK).
• Charles University, Czech Republic, Sep 2015 (KAMAK).
• DIMACS, Rutgers, The State University of New Jersey, USA, Jun–Jul 2015 (REU).
• Department of Computer and Information Science, University of Oregon, USA, Apr 2015 (A. Proskurowski).
• Grenoble Alpes University – Laboratory G-SCOP, France, Dec 2014 (M. Stehlík).
• Charles University, Czech Republic, Sep 2014 (KAMAK).

Organization

• ALGO 2025
• ICALP 2018
• CSGT 2017
• Spring School 2014, 2016, 2017, 2018, 2019
• Homonolo 2015, 2016, 2017, 2018, 2019, 2021

Other (reports, ed.)

1. Spring School 2018 printed in ITI-series.
2. Czech-Slovak conference on Graph Theory 2017 printed in ITI-series.
3. Spring School 2017 printed in ITI-series.
4. Spring School 2016 printed in ITI-series.
5. The report from REU 2015 printed in ITI-series.

PhD Thesis

1. PhD Thesis 2019 at Charles University. [PDF]
2. Extended abstract of PhD Thesis at Charles University. [PDF]

masarik<a>mimuw.edu.pl

CENT building room 03.104, MIMUW, Banacha 2, Warsaw, 02-097, Poland
Room 1650, MIMUW, Banacha 2, Warsaw, 02-097, Poland
Room 8514, Department of Mathematics, Simon Fraser university, 8888 University Drive, Burnaby, V5A 1S6, Canada
Room 320, KAM MFF, Malostranské náměstí 25, Praha 1, 11800, Czech Republic