Publications 2021

• Martin Balko, David Chodounský, Natasha Dobrinen, Jan Hubička, Matěj Konečný, Lluís Vena, and Andy Zucker. Big Ramsey degrees of the generic partial order, the proceedings of the European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2021), Trends in Mathematics, vol 14 , Springer, Cham, pages 637–643, 2021.

• Martin Balko, David Chodounský, Jan Hubička, Matěj Konečný, Jaroslav Nešetřil, and Lluís Vena. Big Ramsey degrees and forbidden cycles, the proceedings of the European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2021), Trends in Mathematics, vol 14 , Springer, Cham, pages 436–441, 2021.

• Martin Balko and Marian Poljak. On off-diagonal ordered Ramsey numbers of nested matchings, the proceedings of the European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2021), Trends in Mathematics, vol 14 , Springer, Cham, pages 241–247, 2021.

• Martin Balko, Manfred Scheucher, and Pavel Valtr. Tight bounds on the expected number of holes in random point sets, the proceedings of the European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2021), Trends in Mathematics, vol 14 , Springer, Cham, pages 411–416, 2021.

• Martin Balko and Máté Vizer. On ordered Ramsey numbers of tripartite 3-uniform hypergraphs, the proceedings of the European Conference on Combinatorics, Graph Theory and Applications  (Eurocomb 2021), Trends in  Mathematics, vol 14 , Springer, Cham, pages 142–147, 2021.

• Martin Balko, Manfred Scheucher, and Pavel Valtr. Holes and islands in random point sets, Random Structures & Algorithms, 2021.

• Martin Balko and Tomáš Čížek. Implementation of Sprouts: a graph drawing game, to appear in the Proceedings of 29th International Symposium on Graph Drawing and Network Visualization (Graph  Drawing 2021), 2021.

• Evans, David M., Jan Hubička, and Jaroslav Nešetřil. "Ramsey properties and extending partial automorphisms forhbox classes of finite structures." Fundamenta Mathematicae 253 (2021): 121-153.

• Evans, David M., Jan Hubička, Matěj Konečný, Yibei Li, and Martin Ziegler. "Simplicity of the automorphism groups of generalised metric spaces." Journal of Algebra (2021).

• Hubička, Jan, Matěj Konečný, and Jaroslav Nešetřil. "Conant's generalised metric spaces are Ramsey." Contributions to Discrete Mathematics 16, no. 2 (2021): 46-70.

• Aranda, Andres, David Bradley-Williams, Eng Keat Hng, Jan Hubička, Miltiadis Karamanlis, Michael Kompatscher, Matěj Konečný, and Micheal Pawliuk. "Completing graphs to metric spaces."  Contributions to Discrete Mathematics 16, no. 2 (2021): 71-89.

• Hubička, J., J. Nešetřil, P. Oviedo, and O. Serra. "On the Homomorphism Order of Oriented Paths and Trees." In Extended Abstracts EuroComb 2021, pp. 739-744. Birkhäuser, Cham, 2021.

• Cherlin, Gregory, Jan Hubička, Matěj Konečný, and Jaroslav Nešetřil. "Ramsey expansions of 3-hypertournaments." In Extended Abstracts EuroComb 2021, Birkhäuser, Cham, 2021.

• Vašek Chvátal, The Discrete Mathematical Charms of Paul Erdős: A Simple Introduction. Cambridge University Press, August 2021.

• Jan Bok, Jirí Fiala, Nikola Jedlicková, Jan Kratochvíl, Michaela Seifrtová: Computational Complexity of Covering Disconnected Multigraphs. in Proceedings FCT 2021: Fundamentals of Computation Theory - 23rd International Symposium, FCT 2021, Athens, Greece, September 12-15, 2021, (E. Bampis, A. Pagourtzis, eds.). Lecture Notes in Computer Science 12867, Springer 2021, ISBN 978-3-030-86592-4, pages 85-99

• Jan Bok, Jirí Fiala, Petr Hlinený, Nikola Jedlicková, Jan Kratochvíl: Computational Complexity of Covering Multigraphs with Semi-Edges: Small Cases. Proceedings MFCS 2021: 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, August 23-27, 2021, Tallinn, Estonia, (F. Bonchi, S. J. Puhlisi, eds.). LIPIcs 202, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2021, ISBN 978-3-95977-201-3, pages 21:1-21:15

• O. Aichholzer, M. Balko, M. Hoffmann, J. Kynčl, W. Mulzer, I. Parada, A. Pilz, M. Scheucher, P. Valtr, B. Vogtenhuber and E. Welzl, Minimal representations of order types by geometric graphs, Journal of Graph Algorithms and Applications 24 (2020), no. 4, 551-572, http://dx.doi.org/10.7155/jgaa.00545

• Ken-ichi Kawarabayashi, Bojan Mohar, Roman Nedela, Peter Zeman: Automorphisms and Isomorphisms of Maps in Linear Time. ICALP 2021: 86:1-86:15

• Pavel Klavík, Dusan Knop, Peter Zeman: Graph isomorphism restricted by lists. Theor. Comput. Sci. 860: 51-71 (2021)

• Steven Chaplick , Fedor V. Fomin , Petr A. Golovach, Dusan Knop , Peter Zeman: Kernelization of Graph Hamiltonicity: Proper H-Graphs. SIAM J. Discret. Math. 35(2):840-892(2021)

• Chaplick, S., Töpfer, M., Voborník, J., Zeman, P. On H-Topological Intersection Graphs. Algorithmica (2021). https://doi.org/10.1007/s00453-021-00846-3

• KAWARABAYASHI, K., KLAVÍK, P., MOHAR, B., NEDELA, R., ZEMAN, P. Isomorphisms of maps on the sphere. In: Polytopes and Discrete Geometry. Providence: American Mathematical Society, 2021. s. 125-147. ISBN 978-1-4704-4897-4, ISSN 0271-4132.

• Elif Garajová, Miroslav Rada, and Milan Hladík. Bilevel linear programming under interval uncertainty. In 39th International Conference on Mathematical Methods in Economics 2021. Conference Proceedings, pp. 123–128, Czech University of Life Sciences Prague, 2021.

• David Hartman, Milan Hladík, and David Říha. Computing the spectral decomposition of interval matrices and a study on interval matrix powers. Appl. Math. Comput., 403:126174:1–13, 2021.

• Milan Hladík. On transformations in interval linear programming: just be careful!. In Proceedings of the 14th International Conference on Strategic Management and its support by Information Systems 2021, pp. 84–91, VŠB - Technical University of Ostrava, Ostrava, 2021.

• Milan Hladík. Stability of the linear complementarity problem properties under interval uncertainty. Cent. Eur. J. Oper. Res., 29:875–889, Sep 2021.

• Milan Hladík. Robust Slater’s condition in an uncertain environment. In 39th International Conference on Mathematical Methods in Economics 2021. Conference Proceedings, pp. 161–166, Czech University of Life Sciences Prague, 2021.

• Milan Hladík. Six ways how to define robust Pareto optimality under double interval uncertainty. In Proceedings of the 16th International Symposium on Operational Research SOR'21, Bled, Slovenia, September 22-24, 2021, pp. 571–576, BISTISK d.o.o., Ljubljana, Slovenia, 2021.

• Milan Hladík, Michal Černý, and Vladik Kreinovich. When is data processing under interval and fuzzy uncertainty feasible: What if few inputs interact? Does feasibility depend on how we describe interaction?. In S.N. Shahbazova et al., editor, Recent Developments and the New Direction in Soft-Computing Foundations and Applications, STUDFUZZ, pp. 91–100, Springer, Cham, 2021.

• Milan Hladík, Michal Černý, and Vladik Kreinovich. Optimization of quadratic forms and t-norm forms on interval domain and computational complexity. In S.N. Shahbazova et al., editor, Recent Developments and the New Direction in Soft-Computing Foundations and Applications, STUDFUZZ, pp. 101–108, Springer, Cham, 2021.

• Milan Hladík, Michal Černý, and Miroslav Rada. A new polynomially solvable class of quadratic optimization problems with box constraints. Optim. Lett., 15(6):2331–2341, September 2021.

• Milan Hladík, David Hartman, and Moslem Zamani. Maximization of a PSD quadratic form and factorization. Optim. Lett., 15(7):2515–2528, October 2021.

• Milan Hladík and Miroslav Rada. The horizontal linear complementarity problem and robustness of the related matrix classes. In B. Dorronsoro et al., editor, Optimization and Learning, CCIS, pp. 350–360, Springer, Cham, 2021.

• Milan Hladík, Lubomir V. Kolev, and Iwona Skalna. Linear interval parametric approach to testing pseudoconvexity. J. Glob. Optim., 79(2):351–368, 2021.

• Saeed Ketabchi, Hossein Moosaei, and Milan Hladík. On the minimum-norm solution of convex quadratic programming. RAIRO-Oper. Res., 55(1):247–260, 2021.

• Hossein Moosaei and Milan Hladík. On the optimal correction of infeasible systems of linear inequalities. J. Optim. Theory Appl., 190(1):32–55, 2021.

• Hossein Moosaei, Saeed Ketabchi, and Milan Hladík. Optimal correction of the absolute value equations. J. Glob. Optim., 79(3):645–667, 2021.

• Iwona Skalna and Milan Hladík. On preconditioning and solving an extended class of interval parametric linear systems. Numer. Algorithms, 87(4):1535–1562, 2021.

• Moslem Zamani and Milan Hladík. A new concave minimization algorithm for the absolute value equation solution. Optim. Lett., 15(6):2241–2254, September 2021.

• Andreas Emil Feldmann, Ashutosh Rai: On Extended Formulations for Parameterized Steiner Trees. In Proceedings of the 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), accepted for publication.

• Jiehua Chen, Wojciech Czerwiński, Yann Disser, Andreas Emil Feldmann, Danny Hermelin, Wojciech Nadara, Marcin Pilipczuk, Michał Pilipczuk, Manuel Sorge, Bartłomiej Wróblewski, Anna Zych-Pawlewicz: Efficient fully dynamic elimination forests with applications to detecting long paths and cycles. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), pp 796-809.

• Yann Disser, Andreas Emil Feldmann, Max Klimm, Jochen Könemann: Travelling on Graphs with Small Highway Dimension. Algorithmica 83(5): 1352-1370 (2021)

• Andreas Emil Feldmann, David Saulpic: Polynomial time approximation schemes for clustering in low highway dimension graphs. J. Comput. Syst. Sci. 122: 72-93 (2021)

• Steffen Borgwardt, Cornelius Brand, Andreas Emil Feldmann, Martin Koutecký: A note on the approximability of deepest-descent circuit steps. Oper. Res. Lett. 49(3): 310-315 (2021)

• Pavel Dvorák, Andreas Emil Feldmann, Dusan Knop, Tomás Masarík, Tomás Toufar, Pavel Veselý: Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices. SIAM J. Discret. Math. 35(1): 546-574 (2021)

• Rajesh Chitnis, Andreas Emil Feldmann, Pasin Manurangsi: Parameterized Approximation Algorithms for Bidirected Steiner Network Problems. ACM Trans. Algorithms 17(2): 12:1-12:68 (2021)

• Fink, Loebl, Pelikánová, Arc-routing for winter road maintenance, Discrete Optimisation 41, 2021.

• D. Baboolal, J. Picado, P. Pillay and A. Pultr, Hewitt’s irresolvability and induced sublocales in spatial frames, Quaestiones Math. 43,11 (2020), 1601-1612

• J. Picado and A. Pultr, Separation in Point-Free Topology, Birkhäuser (Springer Nature Switzerland) (2021) (kniha, ISBN 978-3-030-53478-3)

• J. Picado and A. Pultr, On Equalizers in the Category of Locales, Appl.Categor.Struct. 29 (2021), 267-283 (impaktované)

• J. Picado and A. Pultr, Notes on Point-Free Topology, in: “New Perspectives in Algebra, Topology and Categories” (M.M. Clementino, A. Facchini and M. Gran eds.), Coimbra Math. Texts 1 (Springer 2021), 173-223

• Bellitto, Thomas, Tereza Klimošová, Martin Merker, Marcin Witkowski, and Yelena Yuditsky. "Counterexamples to Thomassen’s conjecture on decomposition of cubic graphs." Graphs and Combinatorics (2021): 1-5.

• Grzesik, Andrzej, Tereza Klimošová, Marcin Pilipczuk, and Michał Pilipczuk. "Covering Minimal Separators and Potential Maximal Cliques in $ P_t $-Free Graphs." The Electronic Journal of Combinatorics (2021): P1-29.

• Jelínek V., Klimošová T., Masařík T., Novotná J., Pokorná A. (2021) On 3-Coloring of  (2𝑃4,𝐶5)-Free Graphs. In: Kowalik Ł., Pilipczuk M., Rzążewski P. (eds) Graph-Theoretic Concepts in Computer Science. WG 2021. Lecture Notes in Computer Science, vol 12911. Springer, Cham.

• A. Shapira and M. Tyomkyn. A Ramsey variant of the Brown-Erdos-Sos conjecture. Bulletin of the London Mathematical Society 53(5) (2021), 1453--1469.

• D. Conlon and M. Tyomkyn. Repeated patterns in proper edge-colourings. SIAM Journal on Discrete Mathematics, 35(3) (2021), 2249--2264.

• A. Shapira and M. Tyomkyn. Quasirandom Graphs and the Pantograph Equation. American Mathematical Monthly 128(7) (2021), 630--639.

• M. Tyomkyn. Many disjoint triangles in co-triangle-free graphs. Combinatorics, Probability and Computing, 30(1) (2021), 153--162.

• M. Amir, A. Shapira and M. Tyomkyn. Two Erdos-Hajnal-type theorems in hypergraphs. Journal of Combinatorial Theory Series B, 146 (2021), 417--438.

• T. Magnard, M. Skotnica, M. Tancer: Shellings and sheddings induced by collapses. SIAM Journal on Discrete Mathematics 35(3) (2021), 1978--2002.

• A. de Mesmay, Y. Rieck, E. Sedgwick, M. Tancer: The unbearable hardness of unknotting. Advances in Mathematics 381 (2021), art. no. 107648.

• D. Bulavka, A. Goodarzi, M. Tancer: Optimal bounds for the colorful fractional Helly theorem. In Proceedings of 37th International Symposium on Computational Geometry (SoCG 2021) 189 (2021), 19:1--19:14.

• Mareš, Martin: Security of Grading Systems. In: Olympiads in Informatics, 2021, Vol. 15, pp. 37-52.

• Jana Novotná, Karolina Okrasa, Michal Pilipczuk, Pawel Rzazewski, Erik Jan van Leeuwen, Bartosz Walczak: Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs. In Algorithmica vol 83(8): 2634-2650 (2021)

• Jan Kratochvíl, Tomáš Masařík, Jana Novotná. U-Bubble Model for Mixed Unit Interval Graphs and Its Applications: The MaxCut Problem Revisited. In Algorithmica, vol 162, available online 2021.

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

• 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. [proceedings link]

• 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, online first, 2021. [journal link], [arXiv]

• Jan Petr, Jan Soukup, On longest palindromic subwords of finite binary words, Discrete Mathematics, Volume 344, Issue 9, 2021, 112493, ISSN 0012-365X, https://doi.org/10.1016/j.disc.2021.112493. (https://www.sciencedirect.com/science/article/pii/S0012365X21002065)

• Elif Garajová and Miroslav Rada. Exact Method for the Worst Optimal Value of an Interval Transportation Problem. In Proceedings of the 16th International Symposium on Operational Research SOR'21, pp. 545–550, Slovenian Society Informatika, Section for Operational Research, 2021.

• Elif Garajová, Miroslav Rada and Milan Hladík. Integer programming reformulations in interval linear programming. In Optimization and Decision Science 2020. AIRO Springer Series, Springer, Cham. [accepted]

• Imre Bárány, Attila Pór, Pavel Valtr: Orientation Preserving Maps of the Square Grid. Proc. Symposium on Compuattional Geometry (SoCG) 2021: 14:1-14:12.

• David Hartman, Aneta Pokorná, Pavel Valtr: On the Connectivity and the Diameter of Betweenness-Uniform Graphs. Proc. of CALDAM 2021. Lecture Notes in Computer Science 12601, 317-330, 2021.

• Stefan Felsner, Laura Merker, Torsten Ueckerdt, Pavel Valtr. Linear Layouts of Complete Graphs. Proceedings of Graph Drawing 2021, LNCS 12868.

• Václav Blažej, Michal Opler, Matas Šileikis, Pavel Valtr: Non-homotopic Loops with a Bounded Number of Pairwise Intersections. Proceedings of Graph Drawing 2021, LNCS 12868.

• Václav Blazej, Michal Opler, Matas Sileikis, Pavel Valtr: On the Intersections of Non-homotopic Loops. Proc. of CALDAM 2021. Lecture Notes in Computer Science 12601, 196-205, 2021.

• Elena Arseneva, Pilar Cano, Linda Kleist, Tamara Mchedlidze, Saeed Mehrabi, Irene Parada, Pavel Valtr: Upward Point Set Embeddings of Paths and Trees. Proc. of WALCOM 2021, Lecture Notes in Computer Science 12635: 234-246, 2021.

• David Auber and Pavel Valtr, Graph Drawing and Network Visualization - 28th International Symposium, GD 2020, Vancouver, BC, Canada, September 16-18, 2020, Revised Selected Papers. Lecture Notes in Computer Science 12590, Springer 2020, ISBN 978-3-030-68765-6.

• Klimošová, Tereza, and Stéphan Thomassé. "Edge‐decomposing graphs into coprime forests." Journal of Graph Theory 97, no. 1 (2021): 21-33.