My Research

My name is Tomáš Masařík and I am an assistant professor at the Institute of Informatics at the The Faculty of Mathematics, Informatics and Mechanics of the University of Warsaw. I participate in the project CUTACOMBS supervised by Marcin Pilipczuk.

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

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

My research interests are in Graph Theory: mostly coloring problems, stuctural graph theory, algorithms, computational complexity, and parameterized complexity. A list of my publications is also presented at Google Scholar and Orcid. My preprints are usually available at arXiv.

Papers

  1. Constricting the Computational Complexity Gap of the $4$-coloring Problem in $(P_t,C_3)$-free Graphs (Justyna Jaworska, Bartłomiej Kielak, TM, Jana Masaříková):
  2. General Strong Bound on the Uncrossed Number which is Tight for the Edge Crossing Number (Gaspard Charvy, TM):
  3. A Tight Meta-theorem for LOCAL Certification of MSO_2 Properties within Bounded Treewidth Graphs (Linda Cook, Eun Jung Kim, TM):
  4. Path Eccentricity and Forbidden Induced Subgraphs (Sylwia Cichacz, Claire Hilaire, TM, Jana Masaříková, Martin Milanič):
  5. Unbent Collections of Orthogonal Drawings (Todor Antić, Giuseppe Liotta, TM, Giacomo Ortali, Matthias Pfretzschner, Peter Stumpf, Alexander Wolff, Johannes Zink):
    • Accepted to WG 2025.
    • arXiv.
  6. Fair Vertex Problems Parameterized by Cluster Vertex Deletion (TM, Jędrzej Olkowski, Anna Zych-Pawlewicz):
  7. On the Uncrossed Number of Graphs (Martin Balko, Petr Hliněný, TM, Joachim Orthaber, Birgit Vogtenhuber, Mirko H. Wagner):
  8. Finding Diverse Solutions Parameterized by Cliquewidth (Karolina Drabik, TM):
  9. Proper Rainbow Saturation Numbers for Cycles (Anastasia Halfpap, Bernard Lidický, TM):
  10. Treewidth is Polynomial in Maximum Degree on Graphs Excluding a Planar Induced Minor (Édouard Bonnet, Jędrzej Hodor, Tuukka Korhonen, TM):
  11. A Generalised Theory of Proportionality in Collective Decision Making (TM, Grzegorz Pierczyński, Piotr Skowron):
  12. Minimizing an Uncrossed Collection of Drawings (Petr Hliněný, TM):
  13. 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):
  14. Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic (Jesse Campion Loth, Kevin Halasz, TM, Bojan Mohar, Robert Šámal):
  15. Proving a Directed Analogue of the Gyárfás-Sumner Conjecture for Orientations of P_4 (Linda Cook, TM, Marcin Pilipczuk, Amadeus Reinald, Uéverton S. Souza):
  16. On Weighted Graph Separation Problems and Flow-augmentation (Eun Jung Kim, TM, Marcin Pilipczuk, Roohani Sharma, Magnus Wahlström):
  17. A Tight Quasi-polynomial Bound for Global Label Min-Cut (Lars Jaffke, Paloma T. Lima, TM, Marcin Pilipczuk, Uéverton S. Souza):
  18. 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):
  19. Max Weight Independent Set in Graphs with no Long Claws: An Analog of the Gyárfás' Path Argument (Konrad Majewski, TM, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, Marek Sokołowski):
  20. List Locally Surjective Homomorphisms in Hereditary Graph Classes (Pavel Dvořák, Monika Krawczyk, TM, Jana Novotná, Paweł Rzążewski, Aneta Żuk):
  21. Single-conflict Colorings of Degenerate Graphs (Peter Bradshaw, TM):
  22. Linear Bounds for Cycle-free Saturation Games (Sean English, TM, Grace McCourt, Erin Meger, Michael S. Ross, Sam Spiro):
  23. Tuza's Conjecture for Threshold Graphs (Marthe Bonamy, Łukasz Bożyk, Andrzej Grzesik, Meike Hatzel, TM, Jana Novotná, Karolina Okrasa):
  24. Robust Connectivity of Graphs on Surfaces (Peter Bradshaw, TM, Jana Novotná, Ladislav Stacho):
  25. Constant Congestion Brambles in Directed Graphs (TM, Marcin Pilipczuk, Paweł Rzążewski, Manuel Sorge):
  26. Random 2-Cell Embeddings of Multistars (Jesse Campion Loth, Kevin Halasz, TM, Bojan Mohar, Robert Šámal):
  27. The Phase Transition of Discrepancy in Random Hypergraphs (Calum MacRury, TM, Leilani Pai, Xavier Pérez-Giménez):
  28. Note on 3-Coloring of (2P_4, C_5)-Free Graphs (Vít Jelínek, Tereza Klimošová, TM, Jana Novotná, Aneta Pokorná):
  29. On Weak Flexibility in Planar Graphs (Bernard Lidický, TM, Kyle Murphy, Shira Zerbib):
  30. Flexible List Colorings in Graphs with Special Degeneracy Conditions (Peter Bradshaw, TM, Ladislav Stacho):
  31. Clique-Width: Harnessing the Power of Atoms (Konrad Dabrowski, TM, Jana Novotná, Daniël Paulusma, Paweł Rzążewski):
  32. 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):
  33. Optimal Discretization is Fixed-parameter Tractable (Stefan Kratsch, TM, Irene Muzi, Marcin Pilipczuk, Manuel Sorge):
  34. U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited (Jiří Kratochvíl, TM, Jana Novotná):
  35. Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View (Radoslav Hušek, Dušan Knop, TM):
  36. Jones' Conjecture in Subcubic Graphs (Marthe Bonamy, François Dross, TM, Andrea Munaro, Wojciech Nadara, Marcin Pilipczuk, Michał Pilipczuk):
  37. FPT Algorithms for Diverse Collections of Hitting Sets (Julien Baste, Lars Jaffke, TM, Geevarghese Philip, Günter Rote):
  38. Packing Directed Circuits Quarter- and Half-Integrally (TM, Irene Muzi, Marcin Pilipczuk, Paweł Rzążewski, Manuel Sorge):
  39. 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):
  40. Flexibility of planar graphs without 4-cycles (TM): [PDF]
  41. Flexibility of planar graphs of girth at least six (Zdeněk Dvořák, TM, Jan Musílek, Ondřej Pangrác): [PDF]
  42. Flexibility of triangle-free planar graphs (Zdeněk Dvořák, TM, Jan Musílek, Ondřej Pangrác):
  43. Steiner Tree Heuristics [PACE 2018 TRACK C] (Radoslav Hušek, Tomáš Toufar, Dušan Knop, TM, Eduard Eiben): [PDF]
  44. Colouring (P_r+P_s)-Free Graphs (Tereza Klimošová, Josef Malík, TM, Jana Novotná, Daniël Paulusma, Veronika Slívová):
  45. Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices (Pavel Dvořák, Andreas Emil Feldmann, Dušan Knop, TM, Tomáš Toufar, Pavel Veselý):
  46. On difference graphs and the local dimension of posets (Jinha Kim, Ryan R. Martin, TM, Warren Shull, Heather C. Smith, Andrew Uzzell, Zhiyu Wang):
  47. Notes on complexity of packing coloring (Minki Kim, Bernard Lidický, TM, Florian Pfender):
  48. Duality gap in interval linear programming (Jana Novotná, Milan Hladík, TM):
  49. Parameterized Complexity of Fair Vertex Evaluation Problems (Dušan Knop, TM, Tomáš Toufar): [PDF]
  50. Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity (Dušan Knop, Martin Koutecký, TM, Tomáš Toufar):
  51. Parameterized complexity of fair deletion problems (TM, Tomáš Toufar):
  52. Anti-Path Cover on Sparse Graph Classes (Pavel Dvořák, Dušan Knop, TM):
  53. Triangle-free planar graphs with the smallest independence number (Zdeněk Dvořák, TM, Jan Musílek, Ondřej Pangrác):
  54. Computational complexity of Distance Edge labeling (Dušan Knop, TM):

Internships / Research Collaboration

Organization

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 astract of PhD Thesis at Charles University. [PDF]

masarik<a>mimuw.edu.pl



CENT building room 03.111, 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