About me

I am currently a postdoctoral researcher in the Department of Algebra at the Faculty of Mathematics and Physics, Charles University, under the supervision of Michael Kompatscher.

I am also a PhD student at the Department of Applied Mathematics at the Faculty of Mathematics and Physics, Charles University. My supervisor is Professor Jan Kratochvíl.

Research interests

• Metaquestions about Constraint Satisfaction Problems
• Graph homomorphisms, colourings, and labellings
• Hamiltonian Path and Cycle problem and their generalization
• Computational complexity of graph problems
• Structural aspects of special graph classes

Contact

You can contact me by email at jedlickova@kam.mff.cuni.cz

Publications

The publications are ordered from newest to oldest. Last updated May 2025.

1. Jan Bok, Avinandan Das, Anna Gujgiczer, and Nikola Jedličková:
   Generalizing Brook's theorem via Partial Coloring is Hard Classically and Locally.
   Submitted, 2025.

2. Jan Bok, Jiří Fiala, Nikola Jedličková, and Jan Kratochvíl:
   Computational complexity of covering regular trees.
   Submitted, 2025.

3. Jan Bok, Santiago Guzmán-Pro, César Hernández-Cruz, and Nikola Jedličková:
   On the expressive power of $2$-edge-colourings of graphs.
   Submitted, 2025. [arXiv]

4. Fedor V. Fomin, Petr A. Golovach, Nikola Jedličková, Jan Kratochvíl, Danil Sagunov, and Kirill Simonov:
   Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective.
   Submitted, 2025. [arXiv]

5. Jan Bok, Nikola Jedličková, Barnaby Martin, Pascal Ochem, Daniël Paulusma, and Siani Smith:
   Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs.
   Journal of Computer and System Sciences, 2025, 103662. [DOI]

6. Nikola Jedličková and Jan Kratochvíl:
   On the Structure of Hamiltonian Graphs with Small Independence Number.
   In Combinatorial Algorithms: 35th International Workshop, IWOCA 2024, Ischia, Italy, July 1–3, 2024, Proceedings, page 180–192. Springer-Verlag, 2024. [DOI]
   Received the Best Paper Award.

7. Jan Bok, Richard C. Brewster, Tomás Feder, Pavol Hell, and Nikola Jedličková:
   List homomorphisms to separable signed graphs.
   Theoretical Computer Science, 1001, 114580, 2024. [DOI]

8. Jan Bok, Richard C. Brewster, Nikola Jedličková, Pavol Hell, and Arash Rafiey:
   Min orderings and list homomorphism dichotomies for signed and unsigned graphs.
   Algorithmica, p. 1-28, 2024. [DOI]

9. Jan Bok, Jiří Fiala, Nikola Jedličková, Jan Kratochvíl, and Michaela Seifrtová:
   Computational Complexity of Covering Disconnected Multigraphs.
   Discrete Applied Mathematics, 359, p. 229-243, 2024. [DOI]

10. Jan Bok, Jiří Fiala, Nikola Jedličková, Jan Kratochvíl, and Paweł Rzążewski:
    List covering of regular multigraphs with semi-edges.
    Algorithmica, 86:782--807, 2024. [DOI],

11. Jan Bok, Jiří Fiala, Petr Hliněný, Nikola Jedličková, and Jan Kratochvíl:
    Computational Complexity of Covering Multigraphs with Semi-Edges: Small Cases.
    Submitted, 2023. [arXiv]

12. Nikola Jedličková and Jan Kratochvíl:
    Hamiltonian path and Hamiltonian cycle are solvable in polynomial time in graphs of bounded independence number.
    [arXiv]

13. Jan Bok, Jiří Fiala, Nikola Jedličková, Jan Kratochvíl, and Michaela Seifrtová:
    Computational Complexity of Covering Colored Mixed Multigraphs with Degree Partition Equivalence Classes of Size at Most Two.
    In Graph-Theoretic Concepts in Computer Science, WG 2023, volume 14093 of Lecture Notes in Computer Science, pages 101-115, 2023. [DOI]

14. Jan Bok, Richard C. Brewster, Tomás Feder, Pavol Hell, and Nikola Jedličková:
    List homomorphism problems for signed trees.
    Discrete Mathematics, 346(3):113257, 2023. [DOI]

15. Jan Bok, Richard C. Brewster, Nikola Jedličková, Pavol Hell, and Arash Rafiey:
    Min orderings and list homomorphism dichotomies for signed and unsigned graphs.
    In LATIN 2022: Theoretical Informatics - 15th Latin American Symposium, volume 13568 of Lecture Notes in Computer Science, pages 510–526, 2022. [DOI]

16. Jan Bok, Jiří Fiala, Nikola Jedličková, Jan Kratochvíl, and Paweł Rzążewski:
    List covering of regular multigraphs.
    In Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, volume 13270 of Lecture Notes in Computer Science, pages 228–242, 2022. [DOI]

17. Jan Bok, Richard C. Brewster, Tomás Feder, Pavol Hell, and Nikola Jedličková:
    List homomorphisms to separable signed graphs.
    In Algorithms and Discrete Applied Mathematics - 8th International Conference, CALDAM 2022, volume 13179 of Lecture Notes in Computer Science, pages 22–35, 2022. [DOI]

18. Jan Bok, Jiří Fiala, Nikola Jedličková, Jan Kratochvíl, and Michaela Seifrtová:
    Computational Complexity of Covering Disconnected Multigraphs.
    In Fundamentals of Computation Theory, FCT 2021, volume 12867 of Lecture Notes in Computer Science, pages 85–89, 2021. [DOI]

19. Jan Bok, Jiří Fiala, Petr Hliněný, Nikola Jedličková, and Jan Kratochvíl:
    Computational Complexity of Covering Multigraphs with Semi-Edges: Small Cases.
    In 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, volume 202 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1–21:15, 2021. [DOI]

20. Jan Bok, and Nikola Jedličková:
    Edge-sum distinguishing labeling.
    Commentationes Mathematicae Universitatis Carolinae 62(2):135–149, 2021. [web]

21. Jan Bok, Nikola Jedličková, Barnaby Martin, Daniël Paulusma, and Siani Smith:
    Injective Colouring for H-Free Graphs.
    In Computer Science – Theory and Applications, CSR 2021, volume 12730 of Lecture Notes in Computer Science, pages 18–30, 2021. [DOI]

22. Jan Bok, Nikola Jedličková, and Jana Maxová:
    A Relaxed Version of Šoltés’s Problem and Cactus Graphs.
    Bulletin of the Malaysian Mathematical Sciences Society, 44:3733–-3745, 2021. [DOI]

23. Jan Bok, Richard C. Brewster, Tomás Feder, Nikola Jedličková, and Pavol Hell:
    List Homomorphism Problems for Signed Graphs.
    In 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, volume 170 of Leibniz International Proceedings in Informatics (LIPIcs), pages 170:20:1–20:14, 2020. [DOI]

24. Jan Bok, Nikola Jedličková, Barnaby Martin, Daniël Paulusma, and Siani Smith:
    Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs.
    In 28th Annual European Symposium on Algorithms, ESA 2020, volume 173 of Leibniz International Proceedings in Informatics (LIPIcs), pages 173:22:1–22:22, 2020. [DOI]

25. Jan Bok, Nikola Jedličková, and Jana Maxová:
    On relaxed Šoltés’s problem.
    Acta Mathematica Universitatis Comenianae 88(3):475–480, 2019. [web]

26. Jan Bok, Boris Furtula, Nikola Jedličková, and Riste Škrekovski:
    On Extremal Graphs of Weighted Szeged Index.
    MATCH 82(1):93–109, 2019. [web]

Active participation in workshops and conferences

• 50th Southeastern International Conference on Combinatorics, Graph Theory and Computing 2019; Boca Raton, FL, USA.
• PhD Summer School in Discrete Mathematics 2019; Rogla, Slovenia.
• 2nd Montenegrin Symposium on Graphs, Informatics and Algebra; 2019, Budva, Montenegro.
• Bordeaux Graph Workshop 2019; Bordeaux, France.
• 51st Southeastern International Conference on Combinatorics, Graph Theory and Computing 2020; Boca Raton, FL, USA.
• 3rd Croatian Combinatorial Days 2020; Zagreb, Croatia.
• The 8th Annual International Conference on Algorithms and Discrete Applied Mathematics CALDAM 2022 (online).
• Combinatorial Constructions Workshop 2022; Zagreb, Croatia.
• 8th Czech-Slovak International Symposium on Graph Theory, Combinatorics, Algorithms and Applications 2022; Prague, Czech Republic.
• Cycles and Colourings 2022; Nový Smokovec, Slovakia.
• Maribor Graph Theory Conference (MGTC) 2022; Maribor, Slovenia.
• 10th Workshop on Graph Classes, Optimization and Width Parameters (GROW) 2022; Koper, Slovenia.
• 11th PhD Summer School in Discrete Mathematics, 2023; Koper, Slovenia.
• KOLKOM 2023: The 40th Colloquium on Combinatorics (Kolloqium über Kombinatorik); Heidelberg, Germany.
• Dutch Days of Combinatorics 2024; Amsterdam, The Netherlands.
• IWOCA 2024: 35th International Workshop on Combinatorial Algorithms; Ischia, Italy.

Participation in schools, tutorials, and workshops (selected)

• 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021); Tallinn, Estonia.
• Summer School: Graphs, Groups, Stochastic Processes; Budapest, Hungary, June 2022.
• The 15th Latin American Theoretical Informatics Symposium (LATIN 2022); Guanajuato, Mexico.
• EPIT 2023 - Le Kaléidoscope de la Complexité; Ile d'Oléron, France, June 2023.
• Structural Graph Theory Bootcamp; Warsaw, Poland, September 2023.
• EPIT 2024 - Graphs and Algorithms: Conjectures; Aussois, France, May 2024.