Jan Kratochvíl

Vít Jelínek, Jan Kratochvíl, Ignaz Rutter: A Kuratowski-type theorem for planarity of partially embedded graphs. Comput. Geom. 46(4): 466-492 (2013)

Jan Kratochvíl, Mirka Miller: Preface. Eur. J. Comb. 34(1): 1-2 (2013)

Jan Kratochvíl, Mirka Miller: Preface. Eur. J. Comb. 34(3): 539-540 (2013)

Jan Kratochvíl, Torsten Ueckerdt: Non-crossing Connectors in the Plane. TAMC 2013: 108-120

Pinar Heggernes, Jan Kratochvíl, Andrzej Proskurowski: Guest editors' foreword. Discrete Applied Mathematics 160(6): 683-684 (2012)

Jirí Fiala, Petr A. Golovach, Jan Kratochvíl, Bernard Lidický, Daniël Paulusma: Distance three labelings of trees. Discrete Applied Mathematics 160(6): 764-779 (2012)

Petr A. Golovach, Jan Kratochvíl, Ondrej Suchý: Parameterized complexity of generalized domination problems. Discrete Applied Mathematics 160(6): 780-792 (2012)

Mathew C. Francis, Jan Kratochvíl, Tomás Vyskocil: Segment representation of a subclass of co-planar graphs. Discrete Mathematics 312(10): 1815-1818 (2012)

Pavel Klavík, Jan Kratochvíl, Tomasz Krawczyk, Bartosz Walczak: Extending Partial Representations of Function Graphs and Permutation Graphs. ESA 2012: 671-682

Pavel Klavík, Jan Kratochvíl, Yota Otachi, Toshiki Saitoh: Extending Partial Representations of Subclasses of Chordal Graphs. ISAAC 2012: 444-454

Konstanty Junosza-Szaniawski, Jan Kratochvíl, Martin Pergel, Pawel Rzazewski: Beyond Homothetic Polygons: Recognition and Maximum Clique. ISAAC 2012: 619-628

James Abello, Pavel Klavík, Jan Kratochvíl, Tomás Vyskocil: MSOL Restricted Contractibility to Planar Graphs. IPEC 2012: 194-205

Martin Doucha, Jan Kratochvíl: Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width. MFCS 2012: 348-359

Konstanty Junosza-Szaniawski, Jan Kratochvíl, Mathieu Liedloff, Pawel Rzazewski: Determining the L(2, 1)-Span in Polynomial Space. WG 2012: 126-137

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: 274-285

Jan Kratochvíl, Torsten Ueckerdt: Non-crossing Connectors in the Plane. CoRR abs/1201.0917 (2012)

Vít Jelínek, Jan Kratochvíl, Ignaz Rutter: A Kuratowski-Type Theorem for Planarity of Partially Embedded Graphs. CoRR abs/1204.2915 (2012)

James Abello, Pavel Klavík, Jan Kratochvíl, Tomás Vyskocil: Matching and l-Subgraph Contractibility to Planar Graphs. CoRR abs/1204.6070 (2012)

Pavel Klavík, Jan Kratochvíl, Tomasz Krawczyk, Bartosz Walczak: Extending partial representations of function graphs and permutation graphs. CoRR abs/1204.6391 (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 abs/1206.5159 (2012)

Pavel Klavík, Jan Kratochvíl, Yota Otachi, Toshiki Saitoh: Extending Partial Representations of Subclasses of Chordal Graphs. CoRR abs/1207.0255 (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 abs/1207.6960 (2012)

Jan Kratochvíl, Michal Vaner: A note on planar partial 3-trees. CoRR abs/1210.8113 (2012)

Frédéric Havet, Martin Klazar, Jan Kratochvíl, Dieter Kratsch, Mathieu Liedloff: Exact Algorithms for L(2, 1)-Labeling of Graphs. Algorithmica 59(2): 169-194 (2011)

Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl, Dieter Kratsch, Mathieu Liedloff: Branch and Recharge: Exact Algorithms for Generalized Domination. Algorithmica 61(2): 252-273 (2011)

Eva Jelínková, Ondrej Suchý, Petr Hlinený, Jan Kratochvíl: Parameterized Problems Related to Seidel's Switching. Discrete Mathematics & Theoretical Computer Science 13(2): 19-44 (2011)

Fedor V. Fomin, Jan Kratochvíl, Daniel Lokshtanov, Federico Mancini, Jan Arne Telle: On the complexity of reconstructing H-free graphs from their Star Systems. Journal of Graph Theory 68(2): 113-124 (2011)

Jirí Fiala, Petr A. Golovach, Jan Kratochvíl: Parameterized complexity of coloring problems: Treewidth versus vertex cover. Theor. Comput. Sci. 412(23): 2513-2523 (2011)

Jan Kratochvíl: Can they cross? and how?: (the hitchhiker's guide to the universe of geometric intersection graphs). Symposium on Computational Geometry 2011: 75-76

Vít Jelínek, Jan Kratochvíl, Ignaz Rutter: A kuratowski-type theorem for planarity of partially embedded graphs. Symposium on Computational Geometry 2011: 107-116

Konstanty Junosza-Szaniawski, Jan Kratochvíl, Mathieu Liedloff, Peter Rossmanith, Pawel Rzazewski: Fast Exact Algorithm for L(2, 1)-Labeling of Graphs. TAMC 2011: 82-93

Pavel Klavík, Jan Kratochvíl, Tomás Vyskocil: Extending Partial Representations of Interval Graphs. TAMC 2011: 276-285

Petr Kolman, Jan Kratochvíl (Eds.): Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Teplá Monastery, Czech Republic, June 21-24, 2011. Revised Papers. Lecture Notes in Computer Science 6986, Springer 2011, isbn 978-3-642-25869-5

Pinar Heggernes, Jan Kratochvíl, Andrzej Proskurowski: Guest Editors' Foreword. Discrete Applied Mathematics 158(7): 729-730 (2010)

Jan Kratochvíl, Jaroslav Nesetril, Zdenek Ryjácek: Preface. Discrete Mathematics 310(3): 371-372 (2010)

Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl, Nicolas Nisse, Karol Suchan: Pursuing a fast robber on a graph. Theor. Comput. Sci. 411(7-9): 1167-1181 (2010)

Boris Horvat, Jan Kratochvíl, Tomaz Pisanski: On the Computational Complexity of Degenerate Unit Distance Representations of Graphs. IWOCA 2010: 274-285

Michael D. Coury, Pavol Hell, Jan Kratochvíl, Tomás Vyskocil: Faithful Representations of Graphs by Islands in the Extended Grid. LATIN 2010: 131-142

Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Vít Jelínek, Jan Kratochvíl, Maurizio Patrignani, Ignaz Rutter: Testing Planarity of Partially Embedded Graphs. SODA 2010: 202-221

Jan Kratochvíl, Angsheng Li, Jirí Fiala, Petr Kolman (Eds.): Theory and Applications of Models of Computation, 7th Annual Conference, TAMC 2010, Prague, Czech Republic, June 7-11, 2010. Proceedings. Lecture Notes in Computer Science 6108, Springer 2010, isbn 978-3-642-13561-3

Jan Kratochvíl, Andrzej Proskurowski, Oriol Serra: Guest editors' foreword. Discrete Applied Mathematics 157(12): 2575-2576 (2009)

Xavier Goaoc, Jan Kratochvíl, Yoshio Okamoto, Chan-Su Shin, Andreas Spillner, Alexander Wolff: Untangling a Planar Graph. Discrete & Computational Geometry 42(4): 542-569 (2009)

Anthony Bonato, Petr A. Golovach, Gena Hahn, Jan Kratochvíl: The capture time of a graph. Discrete Mathematics 309(18): 5588-5595 (2009)

Mitre Costa Dourado, John G. Gimbel, Jan Kratochvíl, Fábio Protti, Jayme Luiz Szwarcfiter: On the computation of the hull number of a graph. Discrete Mathematics 309(18): 5668-5674 (2009)

Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl, Dieter Kratsch, Mathieu Liedloff: Sort and Search: Exact algorithms for generalized domination. Inf. Process. Lett. 109(14): 795-798 (2009)

Eva Jelínková, Jan Kára, Jan Kratochvíl, Martin Pergel, Ondrej Suchý, Tomás Vyskocil: Clustered Planarity: Small Clusters in Cycles and Eulerian Graphs. J. Graph Algorithms Appl. 13(3): 379-422 (2009)

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. Graph Drawing 2009: 304-315

Jirí Fiala, Petr A. Golovach, Jan Kratochvíl: Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover. TAMC 2009: 221-230

Petr A. Golovach, Jan Kratochvíl, Ondrej Suchý: Parameterized Complexity of Generalized Domination Problems. WG 2009: 133-142

Jirí Fiala, Jan Kratochvíl, Mirka Miller (Eds.): Combinatorial Algorithms, 20th International Workshop, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28-July 2, 2009, Revised Selected Papers. Lecture Notes in Computer Science 5874, Springer 2009, isbn 978-3-642-10216-5

Jirí Fiala, Jan Kratochvíl: Locally constrained graph homomorphisms - structure, complexity, and applications. Computer Science Review 2(2): 97-111 (2008)

Jirí Fiala, Jan Kratochvíl, Attila Pór: On the computational complexity of partial covers of Theta graphs. Discrete Applied Mathematics 156(7): 1143-1149 (2008)

Jan Kratochvíl, Martin Pergel: Intersection graphs of homothetic polygons. Electronic Notes in Discrete Mathematics 31: 277-280 (2008)

Vít Jelínek, Eva Jelínková, Jan Kratochvíl, Bernard Lidický: Clustered Planarity: Embedded Clustered Graphs with Two-Component Clusters. Graph Drawing 2008: 121-132

Eva Jelínková, Jan Kratochvíl: On Switching to H-Free Graphs. ICGT 2008: 379-395

Jirí Fiala, Petr A. Golovach, Jan Kratochvíl: Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract). ICALP (1) 2008: 294-305

Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl: On tractability of Cops and Robbers game. IFIP TCS 2008: 171-185

Fedor V. Fomin, Jan Kratochvíl, Daniel Lokshtanov, Federico Mancini, Jan Arne Telle: On the Complexity of Reconstructing H -free Graphs from Their Star Systems. LATIN 2008: 194-205

Jirí Fiala, Petr A. Golovach, Jan Kratochvíl: Distance Constrained Labelings of Trees. TAMC 2008: 125-135

Petr A. Golovach, Jan Kratochvíl: Generalized Domination in Degenerate Graphs: A Complete Dichotomy of Computational Complexity. TAMC 2008: 182-191

Jan Kratochvíl, Josep Díaz, Jirí Fiala: Editorial. Discrete Applied Mathematics 155(2): 79-80 (2007)

Jan Kára, Jan Kratochvíl, David R. Wood: On the Complexity of the Balanced Vertex Ordering Problem. Discrete Mathematics & Theoretical Computer Science 9(1) (2007)

Petr Hlinený, Jan Kratochvíl, Roman Nedela, Martin Skoviera: Preface. Electronic Notes in Discrete Mathematics 28: 1 (2007)

Melanie Badent, Carla Binucci, Emilio Di Giacomo, Walter Didimo, Stefan Felsner, Francesco Giordano, Jan Kratochvíl, Pietro Palladino, Maurizio Patrignani, Francesco Trotta: Homothetic Triangle Contact Representations of Planar Graphs. CCCG 2007: 233-236

Jan Kratochvíl, Martin Pergel: Geometric Intersection Graphs: Do Short Cycles Help? COCOON 2007: 118-128

Xavier Goaoc, Jan Kratochvíl, Yoshio Okamoto, Chan-Su Shin, Alexander Wolff: Moving Vertices to Make Drawings Plane. Graph Drawing 2007: 101-112

Eva Jelínková, Jan Kára, Jan Kratochvíl, Martin Pergel, Ondrej Suchý, Tomás Vyskocil: Clustered Planarity: Small Clusters in Eulerian Graphs. Graph Drawing 2007: 303-314

Jan Kratochvíl, Dieter Kratsch, Mathieu Liedloff: Exact Algorithms for L (2, 1)-Labeling of Graphs. MFCS 2007: 513-524

Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl, Dieter Kratsch, Mathieu Liedloff: Branch and Recharge: Exact Algorithms for Generalized Domination. WADS 2007: 507-518

Petr A. Golovach, Jan Kratochvíl: Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs. WG 2007: 1-11

Xavier Goaoc, Jan Kratochvíl, Yoshio Okamoto, Chan-Su Shin, Alexander Wolff: Moving Vertices to Make Drawings Plane. CoRR abs/0706.1002 (2007)

Hajo Broersma, Fedor V. Fomin, Jan Kratochvíl, Gerhard J. Woeginger: Planar Graph Coloring Avoiding Monochromatic Subgraphs: Trees and Paths Make It Difficult. Algorithmica 44(4): 343-361 (2006)

Daniel Král, Jan Kratochvíl, Andrzej Proskurowski, Heinz-Jürgen Voss: Coloring mixed hypertrees. Discrete Applied Mathematics 154(4): 660-672 (2006)

Jan Kára, Jan Kratochvíl: Fixed Parameter Tractability of Independent Set in Segment Intersection Graphs. IWPEC 2006: 166-174

Michael Kaufmann, Jan Kratochvíl, Katharina Anna Lehmann, Amarendran R. Subramanian: Max-tolerance graphs as intersection graphs: cliques, cycles, and recognition. SODA 2006: 832-841

Jirí Fiala, Jan Kratochvíl: Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy. WG 2006: 15-26

Jan Kratochvíl, Andrzej Proskurowski, Oriol Serra: Structural decompositions, width parameters, and graph labelings. Discrete Applied Mathematics 145(2): 141-142 (2005)

Ton Kloks, Jan Kratochvíl, Haiko Müller: Computing the branchwidth of interval graphs. Discrete Applied Mathematics 145(2): 266-275 (2005)

Jirí Fiala, Jan Kratochvíl, Andrzej Proskurowski: Systems of distant representatives. Discrete Applied Mathematics 145(2): 306-316 (2005)

Jirí Fiala, Jan Kratochvíl, Attila Pór: On the computational complexity of partial covers of Theta graphs. Electronic Notes in Discrete Mathematics 19: 79-85 (2005)

Václav Koubek, Jan Kratochvíl: Preface. Theor. Comput. Sci. 345(2-3): 171-172 (2005)

Jan Kára, Jan Kratochvíl, David R. Wood: On the Complexity of the Balanced Vertex Ordering Problem. COCOON 2005: 849-858

Jirí Fiala, Petr A. Golovach, Jan Kratochvíl: Distance Constrained Labelings of Graphs of Bounded Treewidth. ICALP 2005: 360-372

Jirí Fiala, Jan Kratochvíl: On the Computational Complexity of the L_{(2, 1)}-Labeling Problem for Regular Graphs. ICTCS 2005: 228-236

Daniel Král, Jan Kratochvíl, Heinz-Jürgen Voss: Mixed hypercacti. Discrete Mathematics 286(1-2): 99-113 (2004)

Jirí Fiala, Petr A. Golovach, Jan Kratochvíl: Elegant Distance Constrained Labelings of Trees. WG 2004: 58-67

Jirí Fiala, Václav Koubek, Jan Kratochvíl (Eds.): Mathematical Foundations of Computer Science 2004, 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004, Proceedings. Lecture Notes in Computer Science 3153, Springer 2004, isbn 3-540-22823-3

Daniel Král, Jan Kratochvíl, Heinz-Jürgen Voss: Mixed hypergraphs with bounded degree: edge-coloring of mixed multigraphs. Theor. Comput. Sci. 295: 263-278 (2003)

Jan Kratochvíl, Martin Pergel: Two Results on Intersection Graphs of Polygons. Graph Drawing 2003: 59-70

Jan Kratochvíl: Complexity of Hypergraph Coloring and Seidel's Switching. WG 2003: 297-308

Gena Hahn, Jan Kratochvíl, Jozef Sirán, Dominique Sotteau: On the injective chromatic number of graphs. Discrete Mathematics 256(1-2): 179-192 (2002)

Jirí Fiala, Jan Kratochvíl: Partial covers of graphs. Discussiones Mathematicae Graph Theory 22(1): 89-99 (2002)

Jan Kratochvíl, Zsolt Tuza: On the complexity of bicoloring clique hypergraphs of graphs. J. Algorithms 45(1): 40-54 (2002)

Hubert de Fraysseix, Jan Kratochvíl: Guest Editors' Foreword. J. Graph Algorithms Appl. 6(1): 3-5 (2002)

Jirí Fiala, Jan Kratochvíl, Andrzej Proskurowski: Geometric Systems of Disjoint Representatives. Graph Drawing 2002: 110-117

Hajo Broersma, Fedor V. Fomin, Jan Kratochvíl, Gerhard J. Woeginger: Planar Graph Coloring with Forbidden Subgraphs: Why Trees and Paths Are Dangerous. SWAT 2002: 160-169

Jan Kratochvíl, Zsolt Tuza, Margit Voigt: On the b-Chromatic Number of Graphs. WG 2002: 310-320

Jirí Fiala, Ton Kloks, Jan Kratochvíl: Fixed-parameter complexity of lambda-labelings. Discrete Applied Mathematics 113(1): 59-72 (2001)

Miroslav Fiedler, Jan Kratochvíl, Jaroslav Nesetril: DIMATIA surveys (related to the Fifth Czech and Slovak Symposium on Combinatorics, Graph Theory, Algorithms and Applications held in Prague on July 6-11, 1998). Discrete Mathematics 229(1-3): 1-2 (2001)

Petr Hlinený, Jan Kratochvíl: Representing graphs by disks and balls (a survey of recognition-complexity results). Discrete Mathematics 229(1-3): 101-124 (2001)

Miroslav Fiedler, Jan Kratochvíl, Jaroslav Nesetril: Foreword. Discrete Mathematics 233(1-3): 1-2 (2001)

Luitpold Babel, Ton Kloks, Jan Kratochvíl, Dieter Kratsch, Haiko Müller, Stephan Olariu: Efficient algorithms for graphs with few P₄'s. Discrete Mathematics 235(1-3): 29-51 (2001)

Jirí Fiala, Jan Kratochvíl, Andrzej Proskurowski: Distance Constrained Labeling of Precolored Trees. ICTCS 2001: 285-292

Jirí Fiala, Jan Kratochvíl: Complexity of Partial Covers of Graphs. ISAAC 2001: 537-549

Daniel Král, Jan Kratochvíl, Heinz-Jürgen Voss: Complexity Note on Mixed Hypergraphs. MFCS 2001: 474-486

Daniel Král, Jan Kratochvíl, Zsolt Tuza, Gerhard J. Woeginger: Complexity of Coloring Graphs without Forbidden Induced Subgraphs. WG 2001: 254-262

Magnús M. Halldórsson, Jan Kratochvíl, Jan Arne Telle: Independent Sets with Domination Constraints. Discrete Applied Mathematics 99(1-3): 39-54 (2000)

Jan Kratochvíl, Peter Mihók: Hom-properties are uniquely factorizable into irreducible factors. Discrete Mathematics 213(1-3): 189-194 (2000)

Magnús M. Halldórsson, Jan Kratochvíl, Jan Arne Telle: Mod-2 Independence and Domination in Graphs. Int. J. Found. Comput. Sci. 11(3): 355-363 (2000)

Jan Kratochvíl, Zsolt Tuza: On the complexity of bicoloring clique hypergraphs of graphs (extended abstract). SODA 2000: 40-41

Daniel Král, Jan Kratochvíl, Andrzej Proskurowski, Heinz-Jürgen Voss: Coloring Mixed Hypertrees. WG 2000: 279-289

Jan Kratochvíl, Zsolt Tuza: Rankings of Directed Graphs. SIAM J. Discrete Math. 12(3): 374-384 (1999)

Ton Kloks, Jan Kratochvíl, Haiko Müller: New Branchwidth Territories. STACS 1999: 173-183

Magnús M. Halldórsson, Jan Kratochvíl, Jan Arne Telle: Mod-2 Independence and Domination in Graphs. WG 1999: 101-109

Jirí Fiala, Ton Kloks, Jan Kratochvíl: Fixed-Parameter Complexity of lambda-Labelings. WG 1999: 350-363

Jan Kratochvíl (Ed.): Graph Drawing, 7th International Symposium, GD'99, Stirín Castle, Czech Republic, September 1999, Proceedings. Lecture Notes in Computer Science 1731, Springer 1999, isbn 3-540-66904-3

Jan Kratochvíl, Ales Kubena: On intersection representations of co-planar graphs. Discrete Mathematics 178(1-3): 251-255 (1998)

Jan Kratochvíl, Zsolt Tuza, Margit Voigt: Complexity of choosing subsets from color sets. Discrete Mathematics 191(1-3): 139-148 (1998)

Jan Kratochvíl, Zsolt Tuza, Margit Voigt: Brooks-type theorems for choosability with separation. Journal of Graph Theory 27(1): 43-49 (1998)

Jan Kratochvíl, Andrzej Proskurowski, Jan Arne Telle: On the Complexity of Graph Covering Problems. Nord. J. Comput. 5(3): 173-195 (1998)

Jan Kratochvíl: Crossing Number of Abstract Topological Graphs. Graph Drawing 1998: 238-245

Magnús M. Halldórsson, Jan Kratochvíl, Jan Arne Telle: Independent Sets with Domination Constraints. ICALP 1998: 176-187

Jan Kratochvíl, Zsolt Tuza: Rankings of Directed Graphs. WG 1998: 114-123

Elias Dahlhaus, Jan Kratochvíl, Paul D. Manuel, Mirka Miller: Transversal Partitioning in Balanced Hypergraphs. Discrete Applied Mathematics 79(1-3): 75-89 (1997)

Alexandr V. Kostochka, Jan Kratochvíl: Covering and coloring polygon-circle graphs. Discrete Mathematics 163(1-3): 299-305 (1997)

Jan Kratochvíl, Peter Mihók, Gabriel Semanisin: Graphs maximal with respect to hom-properties. Discussiones Mathematicae Graph Theory 17(1): 77-88 (1997)

Jan Kratochvíl, Ingo Schiermeyer: On the computational complexity of (O, P)-partition problems. Discussiones Mathematicae Graph Theory 17(2): 253-258 (1997)

Jan Kratochvíl, Andrzej Proskurowski, Jan Arne Telle: Covering Regular Graphs. J. Comb. Theory, Ser. B 71(1): 1-16 (1997)

Jan Kratochvíl, András Sebö: Coloring precolored perfect graphs. Journal of Graph Theory 25(3): 207-215 (1997)

Petr Hlinený, Jan Kratochvíl: Computational Complexity of the Krausz Dimension of Graphs. WG 1997: 214-228

Jan Kratochvíl, Andrzej Proskurowski, Jan Arne Telle: Complexity of Colored Graph Covers I. Colored Directed Multigraphs. WG 1997: 242-257

Jan Kratochvíl: Intersection Graphs of Noncrossing Arc-Connected Sets in the Plane. Graph Drawing 1996: 257-270

Michael R. Fellows, Jan Kratochvíl, Martin Middendorf, Frank Pfeiffer: The Complexity of Induced Minors and Related Problems. Algorithmica 13(3): 266-282 (1995)

Jan Kratochvíl, Paul D. Manuel, Mirka Miller: Generalized Domination in Chordal Graphs. Nord. J. Comput. 2(1): 41-50 (1995)

Jan Kratochvíl, Teresa M. Przytycka: Grid Intersection and Box Intersection Graphs on Surfaces (Extended Abstract). Graph Drawing 1995: 365-372

Jan Kratochvíl, Zsolt Tuza: Algorithmic complexity of list colorings. Discrete Applied Mathematics 50(3): 297-302 (1994)

Jan Kratochvíl: A Special Planar Satisfiability Problem and a Consequence of Its NP-completeness. Discrete Applied Mathematics 52(3): 233-252 (1994)

Jan Kratochvíl: Regular codes in regular graphs are difficult. Discrete Mathematics 133(1-3): 191-205 (1994)

Jan Kratochvíl, Zsolt Tuza: Intersection Dimensions of Graph Classes. Graphs and Combinatorics 10(2-4): 159-168 (1994)

Jan Kratochvíl, Jirí Matousek: Intersection Graphs of Segments. J. Comb. Theory, Ser. B 62(2): 289-315 (1994)

Jan Kratochvíl, Andrzej Proskurowski, Jan Arne Telle: Complexity of Graph Covering Problems. WG 1994: 93-105

Jan Kratochvíl, Mirko Krivánek: Satisfiability of Co-Nested Formulas. Acta Inf. 30(4): 397-403 (1993)

Jan Kratochvíl, Petr Savický, Zsolt Tuza: One More Occurrence of Variables Makes Satisfiability Jump From Trivial to NP-Complete. SIAM J. Comput. 22(1): 203-210 (1993)

Jan Kratochvíl, Svatopluk Poljak: Compatible 2-factors. Discrete Applied Mathematics 36(3): 253-266 (1992)

Svante Janson, Jan Kratochvíl: Thresholds for classes of intersection graphs. Discrete Mathematics 108(1-3): 307-326 (1992)

Jan Kratochvíl: String graphs. I. The number of critical nonstring graphs is infinite. J. Comb. Theory, Ser. B 52(1): 53-66 (1991)

Jan Kratochvíl: String graphs. II. recognizing string graphs is NP-hard. J. Comb. Theory, Ser. B 52(1): 67-78 (1991)

Jan Kratochvíl, Jirí Matousek: String graphs requiring exponential representations. J. Comb. Theory, Ser. B 53(1): 1-4 (1991)

Svante Janson, Jan Kratochvíl: Proportional Graphs. Random Struct. Algorithms 2(2): 209-224 (1991)

Jan Kratochvíl, Anna Lubiw, Jaroslav Nesetril: Noncrossing Subgraphs in Topological Layouts. SIAM J. Discrete Math. 4(2): 223-244 (1991)

Michael R. Fellows, Jan Kratochvíl, Matthias Middendorf, Frank Pfeiffer: Induced minors and related problems. Graph Structure Theory 1991: 179-182

Pavol Hell, David G. Kirkpatrick, Jan Kratochvíl, Igor Kríz: On Restricted Two-Factors. SIAM J. Discrete Math. 1(4): 472-484 (1988)

Jan Kratochvíl, Mirko Krivánek: On the Computational Complexity of Codes in Graphs. MFCS 1988: 396-404

Jan Kratochvíl: Perfect codes over graphs. J. Comb. Theory, Ser. B 40(2): 224-228 (1986)