Jan Bok Personal homepage

Jan Bok

I am currently a postdoctoral researcher in ERC Synergy grant POCOCOP, hosted by Libor Barto at the Department of Algebra, a part of the Faculty of Mathematics and Physics, Charles University.

Previously (February 2023–May 2024), I was a postdoctoral researcher at LIMOS laboratory at the University of Clermont Auvergne, hosted by Florent Foucaud.

Even before that I was a PhD student and a part-time researcher at Computer Science Institute, a part of the Faculty of Mathematics and Physics, Charles University. My advisor was Jaroslav Nešetřil (see my genealogy).

Research interests

My current work increasingly uses tools from universal algebra and the algebraic theory of CSPs, in connection with graph homomorphisms, colourings, complexity classifications, and metaquestions on CSPs.

Contact

You can reach me by email at jan.bok@matfyz.cuni.cz.

Publications

The publications are ordered in reverse chronological order. The list includes only accepted and submitted papers, excluding those in preparation.

You can check the following profiles: arXiv, dblp, Google Scholar, ORCID, Scopus, Web of Science ResearcherID, and zbMath. (The profiles do not necessarily contain complete data.)

  1. Jan Bok, Jiří Fiala, Nikola Jedličková, Jan Kratochvíl, and Michaela Seifrtová:
    Computational Complexity of Covering Coloured Mixed Multigraphs with Simple Degree Partitions.
    Discrete Applied Mathematics, 385:194–221, 2026.
    [DOI]
  2. Jan Bok, Avinandan Das, Anna Gujgiczer, and Nikola Jedličková:
    Generalizing Brook's theorem via Partial Coloring is Hard Classically and Locally.
    In WALCOM: Algorithms and Computation, WALCOM 2026, volume 16444 of Lecture Notes in Computer Science, pages 247–262, 2026.
    [DOI], [arXiv]
  3. Jan Bok, Jiří Fiala, Petr Hliněný, Nikola Jedličková, and Jan Kratochvíl:
    Computational Complexity of Covering Multigraphs with Semi-Edges: Small Cases.
    Journal of Computer and System Sciences, 156:103714, 2026.
    [DOI], [arXiv]
  4. Jan Bok, Antoine Dailly, and Tuomo Lehtilä:
    Resolving Sets in Temporal Graphs.
    Submitted, 2026.
    [arXiv], [HAL]
  5. Jan Bok, Jiří Fiala, Nikola Jedličková, and Jan Kratochvíl:
    Computational complexity of covering regular trees.
    In 50th International Symposium on Mathematical Foundations of Computer Science, MFCS 2025, volume 345 of Leibniz International Proceedings in Informatics (LIPIcs), pages 26:1–26:19, 2025.
    [LIPIcs]
  6. 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]
  7. Laurent Beaudou, Jan Bok, Florent Foucaud, Daniel A. Quiroz, and Jean-Florent Raymond:
    Profile and neighbourhood complexity of graphs with excluded minors and tree-structured graphs.
    Submitted, 2025.
    [arXiv]
  8. 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, 154:103662, 2025.
    [DOI], [arXiv], [HAL]
  9. Martin Černý, Jan Bok, David Hartman, and Milan Hladík:
    Positivity and convexity in incomplete cooperative games.
    Annals of Operations Research, 340:785–809, 2024.
    [DOI], [arXiv]
  10. Jan Bok, Richard C. Brewster, Nikola Jedličková, Pavol Hell, and Arash Rafiey:
    Min Orderings and List Homomorphism Dichotomies for Graphs and Signed Graphs.
    Algorithmica, 86:2289–2316, 2024.
    [DOI], [arXiv]
  11. 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], [arXiv]
  12. Jan Bok, Jiří Fiala, Nikola Jedličková, Jan Kratochvíl, and Michaela Seifrtová:
    Computational Complexity of Covering Disconnected Multigraphs.
    Discrete Applied Mathematics, 359:229–243, 2024.
    [DOI], [arXiv]
  13. Jan Bok, Antoine Dailly, and Tuomo Lehtilä:
    Resolving Sets in Temporal Graphs.
    In Combinatorial Algorithms, IWOCA 2024, volume 14764 of Lecture Notes in Computer Science, pages 287–300, 2024.
    [DOI], [arXiv], [HAL]
  14. 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, 2023.
    [DOI], [arXiv]
  15. Jan Bok, and Martin Černý:
    1-convex extensions of incomplete cooperative games and the average value.
    Theory and Decision, 96:239–268, 2024.
    [DOI], [arXiv]
  16. 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]
  17. 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], [arXiv]
  18. 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]
  19. 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]
  20. 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]
  21. 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]
  22. 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]
  23. Jan Bok:
    Cooperative Interval Games and Selections Revisited.
    In Proceedings of the 16th International Symposium on Operational Research in Slovenia, SOR'21, pages 663–669, 2021.
  24. Jan Bok, and Nikola Jedličková:
    Edge-sum distinguishing labeling.
    Commentationes Mathematicae Universitatis Carolinae 62(2):135–149, 2021.
    [DOI], [arXiv]
  25. 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]
  26. 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], [arXiv]
  27. 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]
  28. 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]
  29. Jan Bok, Nikola Jedličková, and Jana Maxová:
    On relaxed Šoltés's problem.
    Acta Mathematica Universitatis Comenianae 88(3):475–480, 2019.
    [journal]
  30. Jan Bok, and Jana Maxová:
    Characterizing subclasses of cover-incomparability graphs by forbidden subposets.
    Order 36(2):349–358, 2019.
    [DOI], [arXiv]
  31. Jan Bok, Boris Furtula, Nikola Jedličková, and Riste Škrekovski:
    On Extremal Graphs of Weighted Szeged Index.
    MATCH 82(1):93–109, 2019.
    [journal], [arXiv]
  32. Jan Bok, and Jaroslav Nešetřil:
    Graph-indexed random walks on pseudotrees.
    Electronic Notes in Discrete Mathematics 68:263–268, 2018.
    [DOI]
  33. Jan Bok, and Milan Hladík:
    Selection-Based Approach to Cooperative Interval Games.
    In Operations Research and Enterprise Systems, ICORES 2015, volume 577 of Communications in Computer and Information Science, pages 40–53, 2015.
    [DOI], [arXiv]