Jan Kratochvíl

ORCID

Publication Activity (10 Years)

Years Active: 1986-2024
Publications (10 Years): 52

Top Venues

Publications

Nikola Jedlicková, Jan Kratochvíl
On the Structure of Hamiltonian Graphs with Small Independence Number. IWOCA (2024)
Nikola Jedlicková, Jan Kratochvíl
On the Structure of Hamiltonian Graphs with Small Independence Number. CoRR (2024)
Jan Bok, Jirí Fiala, Nikola Jedlicková, Jan Kratochvíl, Pawel Rzazewski
List Covering of Regular Multigraphs with Semi-edges. Algorithmica 86 (3) (2024)
Brigt Arve Toppe Håvardstun, Jan Kratochvíl, Joakim Sunde, Jan Arne Telle
On a Combinatorial Problem Arising in Machine Teaching. CoRR (2024)
Jan Bok, Jirí Fiala, Nikola Jedlicková, Jan Kratochvíl, Michaela Seifrtová
Computational complexity of covering disconnected multigraphs. Discret. Appl. Math. 359 (2024)
Jan Kratochvíl, Martin Loebl, Jaroslav Nesetril
Preface: Czech-Slovak Graph Theory in honor of Robin Thomas. Discret. Math. 347 (9) (2024)
Jan Kratochvíl
Graph Covers: Where Topology Meets Computer Science, and Simple Means Difficult. WALCOM (2023)
Sabine Cornelsen, Giordano Da Lozzo, Luca Grilli, Siddharth Gupta, Jan Kratochvíl, Alexander Wolff
The Parametrized Complexity of the Segment Number. GD (2) (2023)
Philipp Kindermann, Jan Kratochvíl, Giuseppe Liotta, Pavel Valtr
Three Edge-disjoint Plane Spanning Paths in a Point Set. CoRR (2023)
Jan Bok, Jirí Fiala, Nikola Jedlicková, Jan Kratochvíl, Michaela Seifrtová
Computational Complexity of Covering Disconnected Multigraphs. CoRR (2023)
Sabine Cornelsen, Giordano Da Lozzo, Luca Grilli, Siddharth Gupta, Jan Kratochvíl, Alexander Wolff
The Parametrized Complexity of the Segment Number. CoRR (2023)
Jan Bok, Jirí Fiala, Nikola Jedlicková, Jan Kratochvíl, Michaela Seifrtová
Computational Complexity of Covering Colored Mixed Multigraphs with Degree Partition Equivalence Classes of Size at Most Two (Extended Abstract). WG (2023)
Nikola Jedlicková, Jan Kratochvíl
Hamiltonian path and Hamiltonian cycle are solvable in polynomial time in graphs of bounded independence number. CoRR (2023)
Luca Grilli, Seok-Hee Hong, Jan Kratochvíl, Ignaz Rutter
Drawing Simultaneously Embedded Graphs with Few Bends. Int. J. Found. Comput. Sci. 34 (7) (2023)
Philipp Kindermann, Jan Kratochvíl, Giuseppe Liotta, Pavel Valtr
Three Edge-Disjoint Plane Spanning Paths in a Point Set. GD (1) (2023)
Deniz Agaoglu Çagirici, Onur Çagirici, Jan Derbisz, Tim A. Hartmann, Petr Hlinený, Jan Kratochvíl, Tomasz Krawczyk, Peter Zeman
Recognizing H-Graphs - Beyond Circular-Arc Graphs. MFCS (2023)
Robert Ganian, Jan Kratochvíl, Stefan Szeider
Preface: Ninth workshop on graph classes, optimization, and Width Parameters, Vienna, Austria. Discret. Appl. Math. 312 (2022)
Jan Bok, Jirí Fiala, Nikola Jedlicková, Jan Kratochvíl, Pawel Rzazewski
List Covering of Regular Multigraphs. IWOCA (2022)
Michael A. Bekos, Stefan Felsner, Philipp Kindermann, Stephen G. Kobourov, Jan Kratochvíl, Ignaz Rutter
The Rique-Number of Graphs. GD (2022)
Michael A. Bekos, Stefan Felsner, Philipp Kindermann, Stephen G. Kobourov, Jan Kratochvíl, Ignaz Rutter
The Rique-Number of Graphs. CoRR (2022)
Deniz Agaoglu Çagirici, Onur Çagirici, Jan Derbisz, Tim A. Hartmann, Petr Hlinený, Jan Kratochvíl, Tomasz Krawczyk, Peter Zeman
Beyond circular-arc graphs - recognizing lollipop graphs and medusa graphs. CoRR (2022)
Jan Bok, Jirí Fiala, Nikola Jedlicková, Jan Kratochvíl, Pawel Rzazewski
List covering of regular multigraphs. CoRR (2022)
Jan Bok, Jirí Fiala, Petr Hlinený, Nikola Jedlicková, Jan Kratochvíl
Computational Complexity of Covering Multigraphs with Semi-Edges: Small Cases. MFCS (2021)
Michael Kaufmann, Jan Kratochvíl, Fabian Lipp, Fabrizio Montecchiani, Chrysanthi N. Raftopoulou, Pavel Valtr
The Stub Resolution of 1-planar Graphs. J. Graph Algorithms Appl. 25 (2) (2021)
Jan Bok, Jirí Fiala, Nikola Jedlicková, Jan Kratochvíl, Michaela Seifrtová
Computational Complexity of Covering Disconnected Multigraphs. FCT (2021)
Jan Bok, Jirí Fiala, Petr Hlinený, Nikola Jedlicková, Jan Kratochvíl
Computational Complexity of Covering Two-vertex Multigraphs with Semi-edges. CoRR (2021)
Jan Kratochvíl, Tomás Masarík, Jana Novotná
-Bubble Model for Mixed Unit Interval Graphs and Its Applications: The MaxCut Problem Revisited. Algorithmica 83 (12) (2021)
Jan Kratochvíl, Tomás Masarík, Jana Novotná
U-Bubble Model for Mixed Unit Interval Graphs and Its Applications: The MaxCut Problem Revisited. MFCS (2020)
Michael Kaufmann, Jan Kratochvíl, Fabian Lipp, Fabrizio Montecchiani, Chrysanthi N. Raftopoulou, Pavel Valtr
The Stub Resolution of 1-Planar Graphs. WALCOM (2020)
Jan Kratochvíl, Tomás Masarík, Jana Novotná
U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited. CoRR (2020)
Dariusz Dereniowski, Tomas Gavenciak, Jan Kratochvíl
Cops, a fast robber and defensive domination on interval graphs. Theor. Comput. Sci. 794 (2019)
Alexandre Talon, Jan Kratochvíl
Completion of the mixed unit interval graphs hierarchy. J. Graph Theory 87 (3) (2018)
Tomas Gavenciak, Przemyslaw Gordinowicz, Vít Jelínek, Pavel Klavík, Jan Kratochvíl
Cops and Robbers on intersection graphs. Eur. J. Comb. 72 (2018)
Jan Kratochvíl, Zsuzsanna Lipták
Preface. Eur. J. Comb. 68 (2018)
Jirí Fiala, Tomas Gavenciak, Dusan Knop, Martin Koutecký, Jan Kratochvíl
Parameterized complexity of distance labeling and uniform channel assignment problems. Discret. Appl. Math. 248 (2018)
Valentin E. Brimkov, Konstanty Junosza-Szaniawski, Sean Kafer, Jan Kratochvíl, Martin Pergel, Pawel Rzazewski, Matthew Szczepankiewicz, Joshua Terhaar
Homothetic polygons and beyond: Maximal cliques in intersection graphs. Discret. Appl. Math. 247 (2018)
Jirí Fiala, Pavel Klavík, Jan Kratochvíl, Roman Nedela
3-connected reduction for regular graph covers. Eur. J. Comb. 73 (2018)
Michael Kaufmann, Jan Kratochvíl, Fabian Lipp, Fabrizio Montecchiani, Chrysanthi N. Raftopoulou, Pavel Valtr
Bounded Stub Resolution for Some Maximal 1-Planar Graphs. CALDAM (2018)
Patrizio Angelini, Steven Chaplick, Felice De Luca, Jirí Fiala, Jaroslav Hancl Jr., Niklas Heinsohn, Michael Kaufmann, Stephen G. Kobourov, Jan Kratochvíl, Pavel Valtr
On Vertex- and Empty-Ply Proximity Drawings. Graph Drawing (2017)
Carla Binucci, Markus Chimani, Walter Didimo, Martin Gronemann, Karsten Klein, Jan Kratochvíl, Fabrizio Montecchiani, Ioannis G. Tollis
Algorithms and Characterizations for 2-Layer Fan-planarity: From Caterpillar to Stegosaurus. J. Graph Algorithms Appl. 21 (1) (2017)
James Abello, Pavel Klavík, Jan Kratochvíl, Tomás Vyskocil
MSOL restricted contractibility to planar graphs. Theor. Comput. Sci. 676 (2017)
Pavel Klavík, Jan Kratochvíl, Yota Otachi, Ignaz Rutter, Toshiki Saitoh, Maria Saumell, Tomás Vyskocil
Extending Partial Representations of Proper and Unit Interval Graphs. Algorithmica 77 (4) (2017)
Pavel Klavík, Jan Kratochvíl, Yota Otachi, Toshiki Saitoh, Tomás Vyskocil
Extending Partial Representations of Interval Graphs. Algorithmica 78 (3) (2017)
Patrizio Angelini, Steven Chaplick, Felice De Luca, Jirí Fiala, Jan Hancl Jr., Niklas Heinsohn, Michael Kaufmann, Stephen G. Kobourov, Jan Kratochvíl, Pavel Valtr
On Vertex- and Empty-Ply Proximity Drawings. CoRR (2017)
Jan Kratochvíl, Jan Arne Telle, Marek Tesar
Computational complexity of covering three-vertex multigraphs. Theor. Comput. Sci. 609 (2016)
Jirí Fiala, Tomas Gavenciak, Dusan Knop, Martin Koutecký, Jan Kratochvíl
Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems - (Extended Abstract). COCOON (2016)
Jirí Fiala, Pavel Klavík, Jan Kratochvíl, Roman Nedela
Algorithmic Aspects of Regular Graph Covers. CoRR (2016)
Patrizio Angelini, Steven Chaplick, Sabine Cornelsen, Giordano Da Lozzo, Giuseppe Di Battista, Peter Eades, Philipp Kindermann, Jan Kratochvíl, Fabian Lipp, Ignaz Rutter
Simultaneous Orthogonal Planarity. Graph Drawing (2016)
Patrizio Angelini, Steven Chaplick, Sabine Cornelsen, Giordano Da Lozzo, Giuseppe Di Battista, Peter Eades, Philipp Kindermann, Jan Kratochvíl, Fabian Lipp, Ignaz Rutter
Simultaneous Orthogonal Planarity. CoRR (2016)
Vít Jelínek, Eva Jelínková, Jan Kratochvíl
On the hardness of switching to a small number of edges. CoRR (2016)
Vít Jelínek, Eva Jelínková, Jan Kratochvíl
On the Hardness of Switching to a Small Number of Edges. COCOON (2016)
Tomas Gavenciak, Przemyslaw Gordinowicz, Vít Jelínek, Pavel Klavík, Jan Kratochvíl
Cops and Robbers on Intersection Graphs. CoRR (2016)
Jirí Fiala, Tomas Gavenciak, Dusan Knop, Martin Koutecký, Jan Kratochvíl
Distance constrained labeling on graphs with bounded neighborhood diversity. CoRR (2015)
Alexandre Talon, Jan Kratochvíl
Completion of the Mixed Unit Interval Graphs Hierarchy. TAMC (2015)
Carla Binucci, Markus Chimani, Walter Didimo, Martin Gronemann, Karsten Klein, Jan Kratochvíl, Fabrizio Montecchiani, Ioannis G. Tollis
2-Layer Fan-Planarity: From Caterpillar to Stegosaurus. Graph Drawing (2015)
Pavel Klavík, Jan Kratochvíl, Yota Otachi, Toshiki Saitoh
Extending partial representations of subclasses of chordal graphs. Theor. Comput. Sci. 576 (2015)
Tomas Gavenciak, Przemyslaw Gordinowicz, Vít Jelínek, Pavel Klavík, Jan Kratochvíl
Cops and Robbers on String Graphs. ISAAC (2015)
Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Vít Jelínek, Jan Kratochvíl, Maurizio Patrignani, Ignaz Rutter
Testing Planarity of Partially Embedded Graphs. ACM Trans. Algorithms 11 (4) (2015)
Tomas Gavenciak, Jan Kratochvíl, Pawel Pralat
Firefighting on square, hexagonal, and triangular grids. Discret. Math. 337 (2014)
Jirí Fiala, Pavel Klavík, Jan Kratochvíl, Roman Nedela
Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs. CoRR (2014)
Jan Kratochvíl, Jan Arne Telle, Marek Tesar
Computational Complexity of Covering Three-Vertex Multigraphs. MFCS (2) (2014)
Luca Grilli, Seok-Hee Hong, Jan Kratochvíl, Ignaz Rutter
Drawing Simultaneously Embedded Graphs with Few Bends. Graph Drawing (2014)
Pinar Heggernes, Jan Kratochvíl, Sang-il Oum
Guest editors' foreword. Discret. Appl. Math. 168 (2014)
Pavel Klavík, Jan Kratochvíl, Yota Otachi, Ignaz Rutter, Toshiki Saitoh, Maria Saumell, Tomás Vyskocil
Extending Partial Representations of Proper and Unit Interval Graphs. SWAT (2014)
Giordano Da Lozzo, Vít Jelínek, Jan Kratochvíl, Ignaz Rutter
Planar Embeddings with Small and Uniform Faces. CoRR (2014)
Steven Chaplick, Paul Dorbec, Jan Kratochvíl, Mickaël Montassier, Juraj Stacho
Contact Representations of Planar Graphs: Extending a Partial Representation is Hard. WG (2014)
Jan Kratochvíl, Mark H. Siggers
Locally injective k-colourings of planar graphs. Discret. Appl. Math. 173 (2014)
Alexandre Talon, Jan Kratochvíl
Completion of the mixed unit interval graphs hierarchy. CoRR (2014)
Giordano Da Lozzo, Vít Jelínek, Jan Kratochvíl, Ignaz Rutter
Planar Embeddings with Small and Uniform Faces. ISAAC (2014)
Valentin E. Brimkov, Konstanty Junosza-Szaniawski, Sean Kafer, Jan Kratochvíl, Martin Pergel, Pawel Rzazewski, Matthew Szczepankiewicz, Joshua Terhaar
Homothetic Polygons and Beyond: Intersection Graphs, Recognition, and Maximum Clique. CoRR (2014)
Jirí Fiala, Pavel Klavík, Jan Kratochvíl, Roman Nedela
Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs. ICALP (1) (2014)
Eva Jelínková, Jan Kratochvíl
-Free Graphs. J. Graph Theory 75 (4) (2014)
Jan Kratochvíl, Mirka Miller
Preface. Eur. J. Comb. 34 (1) (2013)
Pavel Klavík, Jan Kratochvíl, Yota Otachi, Toshiki Saitoh, Tomás Vyskocil
Linear-time Algorithm for Partial Representation Extension of Interval Graphs. CoRR (2013)
Jan Kratochvíl, Mirka Miller
Preface. Eur. J. Comb. 34 (3) (2013)
Tomas Gavenciak, Vít Jelínek, Pavel Klavík, Jan Kratochvíl
Cops and Robbers on Intersection Graphs. ISAAC (2013)
Vít Jelínek, Jan Kratochvíl, Ignaz Rutter
A Kuratowski-type theorem for planarity of partially embedded graphs. Comput. Geom. 46 (4) (2013)
Jirí Fiala, Jan Kratochvíl, Angsheng Li
Preface. Theor. Comput. Sci. 494 (2013)
Konstanty Junosza-Szaniawski, Jan Kratochvíl, Mathieu Liedloff, Pawel Rzazewski
(2, 1)L(2, 1)-span in polynomial space. Discret. Appl. Math. 161 (13-14) (2013)
Konstanty Junosza-Szaniawski, Jan Kratochvíl, Mathieu Liedloff, Peter Rossmanith, Pawel Rzazewski
Fast exact algorithm for L(2, 1)-labeling of graphs. Theor. Comput. Sci. 505 (2013)
Vít Jelínek, Eva Jelínková, Jan Kratochvíl, Bernard Lidický, Marek Tesar, Tomás Vyskocil
The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree. Graphs Comb. 29 (4) (2013)
Jan Kratochvíl, Torsten Ueckerdt
Non-crossing Connectors in the Plane. TAMC (2013)
James Abello, Pavel Klavík, Jan Kratochvíl, Tomás Vyskocil
Matching and l-Subgraph Contractibility to Planar Graphs CoRR (2012)
Pavel Klavík, Jan Kratochvíl, Tomasz Krawczyk, Bartosz Walczak
Extending partial representations of function graphs and permutation graphs CoRR (2012)
Pavel Klavík, Jan Kratochvíl, Yota Otachi, Ignaz Rutter, Toshiki Saitoh, Maria Saumell, Tomás Vyskocil
Extending Partial Representations of Proper and Unit Interval Graphs CoRR (2012)
Pinar Heggernes, Jan Kratochvíl, Andrzej Proskurowski
Guest editors' foreword. Discret. Appl. Math. 160 (6) (2012)
Jan Kratochvíl, Torsten Ueckerdt
Non-crossing Connectors in the Plane CoRR (2012)
Konstanty Junosza-Szaniawski, Jan Kratochvíl, Mathieu Liedloff, Pawel Rzazewski
Determining the L(2, 1)-Span in Polynomial Space. WG (2012)
Steven Chaplick, Vít Jelínek, Jan Kratochvíl, Tomás Vyskocil
Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill. WG (2012)
Jirí Fiala, Petr A. Golovach, Jan Kratochvíl, Bernard Lidický, Daniël Paulusma
Distance three labelings of trees. Discret. Appl. Math. 160 (6) (2012)
Pavel Klavík, Jan Kratochvíl, Yota Otachi, Toshiki Saitoh
Extending Partial Representations of Subclasses of Chordal Graphs. ISAAC (2012)
Jan Kratochvíl, Michal Vaner
A note on planar partial 3-trees CoRR (2012)
Pavel Klavík, Jan Kratochvíl, Yota Otachi, Toshiki Saitoh
Extending Partial Representations of Subclasses of Chordal Graphs CoRR (2012)
Mathew C. Francis, Jan Kratochvíl, Tomás Vyskocil
Segment representation of a subclass of co-planar graphs. Discret. Math. 312 (10) (2012)
Martin Doucha, Jan Kratochvíl
Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width. MFCS (2012)
Pavel Klavík, Jan Kratochvíl, Tomasz Krawczyk, Bartosz Walczak
Extending Partial Representations of Function Graphs and Permutation Graphs. ESA (2012)
Vít Jelínek, Jan Kratochvíl, Ignaz Rutter
A Kuratowski-Type Theorem for Planarity of Partially Embedded Graphs CoRR (2012)
Steven Chaplick, Vít Jelínek, Jan Kratochvíl, Tomás Vyskocil
Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill CoRR (2012)
James Abello, Pavel Klavík, Jan Kratochvíl, Tomás Vyskocil
MSOL Restricted Contractibility to Planar Graphs. IPEC (2012)
Petr A. Golovach, Jan Kratochvíl, Ondrej Suchý
Parameterized complexity of generalized domination problems. Discret. Appl. Math. 160 (6) (2012)

Jan Kratochvíl.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Jan Kratochvíl