My research

My name is Jana Novotná and I am a third-year doctoral student.

My principal research interest lie in structural and algorithmic graph theory, in particular graph coloring problems, and computational and parametrized complexity.

You can find my Google Scholar profile and ORCID profile.

Publications

• Separator Theorem and Algorithms for Planar Hyperbolic Graphs (Sándor Kisfaludi-Bak, Erik Jan van Leeuwen, Bartosz Walczak, Karol Węgrzycki)
  • Preprint at arXiv.


• Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument (Konrad Majewski, Tomáš Masařík, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, Marek Sokolowski)
  • Preprint at arXiv.
  • ICALP 2022 (proceedings).
  • Journal version: ACM Transactions on Computation Theory, June 2024.


• List Locally Surjective Homomorphisms in Hereditary Graph Classes (Pavel Dvořák, Monika Krawczyk, Tomáš Masařík, Paweł Rzążewski, Aneta Żuk)
  • Preprint at arXiv.
  • ISAAC 2022 (proceedings).


• Taming graphs with no large creatures and skinny ladders (Jakub Gajarský, Lars Jaffke, Paloma T. Lima, Marcin Pilipczuk, Paweł Rzążewski, Uéverton S. Souza)
  • Preprint at arXiv.
  • ESA 2022 (proceedings).


• Tuza's Conjecture for Threshold Graphs (Marthe Bonamy, Lukasz Bożyk, Andrzej Grzesik, Meike Hatzel, Tomáš Masařík, Jana Novotná, Karolina Okrasa)
  • Preprint at arXiv.
  • EuroComb 2021 (proceedings).
  • Journal version: Discrete Mathematics & Theoretical Computer Science, August 2022.


• Robust Connectivity of Graphs on Surfaces (Peter Bradshaw, Tomáš Masařík, Jana Novotná, Ladislav Stacho)
  • Preprint at arXiv.
  • EuroComb 2021 (proceedings).
  • Journal version: SIAM Journal on Discrete Mathematics, March 2022.


• Note on 3-Coloring of (2P_4,C_5)-Free Graphs (Vít Jelínek, Tereza Klimošová, Tomáš Masařík, Jana Novotná, Aneta Pokorná)
  • Preprint at arXiv.
  • WG 2021 (proceedings).
  • Journal version: Algorithmica, February 2022.
  
  
• Vertex deletion into bipartite permutation graphs (Łukasz Bożyk, Jan Derbisz, Tomasz Krawczyk, Jana Novotná, Karolina Okrasa)
  • Preprint at arXiv.
  • IPEC 2020, co-winner of Best paper & Best student paper (proceedings).
  • Journal version: Algorithmica, February 2022.


• Clique-Width: Harnessing the Power of Atoms (Konrad K. Dabrowski, Tomás Masarík, Jana Novotná, Daniël Paulusma, Paweł Rzążewski)
  • Preprint at arXiv.
  • WG 2020 (proceedings).
  • Journal version: Journal of Graph Theory, July 2023.


• U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited (Jan Kratochvíl, Tomáš Masařík, Jana Novotná)
  • Preprint at arXiv.
  • MFCS 2020 (proceedings).
  • Journal version: Algorithmica, July 2021.
  
  
• Subexponential algorithms for finding large induced sparse subgraphs (Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, Erik Jan van Leeuwen, Bartosz Walczak)
  • Preprint at arXiv,
  • IPEC 2019,
  • Journal version: Algorithmica, July 2020.


• Colouring (P_r+P_s)-Free Graphs (Tereza Klimošová, Josef Malík, Tomáš Masařík, Jana Novotná, Daniël Paulusma, Veronika Slívová)
  • Preprint at arXiv,
  • In ISAAC 2018,
  • Journal version: Algorithmica, January 2020.


• On the Simultaneous Minimum Spanning Trees Problem (Matěj Konečný, Stanislav Kučera, Jana Novotná, Jakub Pekárek, Martin Smolík, Jakub Tětek, Martin Töpfer)
  • Preprint at arXiv,
  • In CALDAM 2018.


• Minimal Sum Labeling of Graphs (Matěj Konečný, Stanislav Kučera, Jana Novotná, Jakub Pekárek, Štěpán Šimsa, Martin Töpfer).
  • Preprint at arXiv,
  • In IWOCA 2017,
  • Journal version: Journal of Discrete Algorithms, Volumes 52–53, September 2018, Pages 29-37.
  
  
• Duality gap in interval linear programming (Jana Novotná, Milan Hladík, Tomáš Masařík).
  • Preprint at arXiv,
  • In SOR17,
  • Journal version: Journal of Optimization Theory and Applications, Volume 184, Issue 2, February 2020, Pages 565–580.

Internships and Research Colaboration

• Simon Fraser University, Canada, March 2020 – July 2021 (Ladislav Stacho).
• Warsaw University of Technology, Poland, November 26 – December 2, 2018 (Paweł Rzążewski).
• Durham University, UK, November 9 – 16, 2018; 28 April – 10 May, 2019 (Daniël Paulusma).
• University of Bergen, Norway, January - June 2018 (Erasmus+).
• DIMACS, Rutgers, The State University of New Jersey, US, May – July, 2017 (REU).