List of publications

Jan Kratochvil

• String graphs, in: Graphs and Other Combinatorial Topics, Proceedings Third Czechoslovak Symposium on Graph Theory, Prague 1982, Teubner Texte zur Mathematik 59, Berlin 1983, pp 168-172 (MR 85e:05142)
• Graphs and associative triples in quasitrivial groupoids (with T.Kepka), Comment. Math. Univ. Carolin. 25 (1984), 697-684 (MR 86f:20070)
• One-perfect codes over selfcomplementary graphs, Comment. Math. Univ. Carolin. 26 (1985), 589-595 (MR 87b:94049)
• Perfect codes over graphs, J. Combin. Theory Ser. B 40 (1986), 224-228 (MR 87e:94052)
• On Hamiltonian cycles in two-triangle graphs (with D. Zeps), in: Proceedings XV Winter School at Srn\'{\i 1987, Acta Univ. Carolin. 28 (1987), pp 73-78 (MR 89b:05117)
• Perfect codes in general graphs, Colloquia Math. Soc. J. Bolyai 52, Proceedings VIIth Hungarian Colloqium on Combinatorics, Eger 1987, pp 357-364
• On the minimum number of Hamiltonian cycles in triangulations (with D. Zeps), J. Graph Theory 12 (1988), 191-194 (MR 89g:05074)
• On restricted two-factors (with P. Hell, D. Kirkpatrick and I. Kriz), SIAM J. Discr. Math. 1 (1988), 472-484 (MR 89m:05092)
• Perfect codes and two-graphs, Comment. Math. Univ. Carolin. 30 (1989), 755-760 (MR 91a:05080)
• NP-hardness results for intersection graphs (with J. Matousek), Comment. Math. Univ. Carolin. 30 (1989), 761-773 (MR 91c:05156)
• On the existence of perfect codes in a random graph (with J. Maly and J. Matous>ek), in: Proceedings Random Graphs '87, Wiley 1990, pp. 141-149 (MR 92e:05103)
• INDEPENDENT SET and CLIQUE problems in intersection defined classes of graphs (with J. Nesetril), Comment. Math. Univ. Carolin. 31 (1990), 85-93 (MR 91g:05125)
• Proportional graphs (with S. Janson), Random Struct. Alg. 2 (1991), 209-224 (MR 92a:05119)
• String graphs I. There are infinitely many critical nonstring graphs, J. Combin. Theory Ser. B 52 (1991), 53-66 (MR 92g:05156)
• String graphs II. Recognizing string graphs is NP-hard, J. Combin. Theory Ser. B 52 (1991), 67-78 (MR 92g:05157)
• String graphs requiring exponential representations (with J. Matousek), J. Combin. Theory Ser. B 53 (1991), 1-4 (MR 92g:05080)
• Noncrossing subgraphs of topological layouts (with A. Lubiw and J. Nesetril), SIAM J. Discrete Math. 4 (1991), 223-244 (MR 92e:05111)
• On the computational complexity of Seidel's switching (with J. Nesetril and O. Zyka), in: Combinatorics, Graphs and Complexity (M.Fiedler and J.Nesetril eds.), Proceedings 4th Czechoslovak Symposium on Combinatorics, Prachatice 1990, Annals of Discrete Math. 51, North Holland, Amsterdam, 1992 (MR 93j:05156)
• Compatible two-factors (with S. Poljak), Discrete Appl. Math. 36 (1992), 253-266 (MR 93i:05100)
• Threshold functions for classes of intersection graphs (with S. Janson), Discrete Math. 108 (1992), 307-326 (MR 93h:05143)
• One more occurrence of variables makes satisfiability jump from trivial to NP-complete (with P. Savicky and Z. Tuza), SIAM J. Comput. 22 (1993), 203-210 (MR 94a:68038)
• Satisfiability of co-nested formulas (with M. Krivanek) Acta Informatica 30 (1993), 397-403 (MR 94g:03079)
• Precoloring extension with fixed color bound Acta Math. Univ. Comen. 62 (1993) 139-153
• A special planar satisfiability problem and some consequences of its NP-completeness, Discrete Appl. Math. 52 (1994), 233-252
• Intersection graphs of segments (with J. Matousek), J. Combin. Th. Ser. B 68 (1994), 317-339
• Regular codes in regular graphs are difficult Discrete Math. 133 (1994), 191-205
  • [partly based on On the computational complexity of codes in graphs (with M. Krivanek), in: Proceedings MFCS Karlovy Vary 1988, Lecture Notes in Comp. Sci. 324, Springer-Verlag, Berlin 1988, pp 396-404 (MR 90i:68010)]
• Intersection dimensions of graph classes (with Zs. Tuza) Graphs and Combinatorics 10 (1994) 159-168
• Algorithmic complexity of list colorings (with Zs. Tuza) Discrete Appl. Math. 50 (1994) 297-302
• The complexity of induced minors and related problems (with M. Fellows, M.Middendorf and F.Pfeiffer) Algorithmica 13 (1995), 266-282
  • [extended abstract published as The complexity of induced minors (extended abstract) (with M.R.Fellows, M.Middendorf and F.Pfeiffer), In: Graph Structure Theory (Robertson and Seymour eds.), Proceedings of Joint Summer Research Conference on Graph Minors, Seattle 1991, Contemporary Mathematics 147, AMS, Providence, 1993, pp.179-182]
• Grid intersection and box intersection graphs on surfaces (extended abstract) (with T. Przytycka) In: Graph Drawing (F.J.Brandenburg ed.), Proceedings Graph Drawing '95, Passau, September 1995, Lecture Notes in Computer Science 1027, Springer Verlag, Berlin Heidelberg, 1995, pp. 365-372
• $k$-Ramsey classes and dimensions of graphs Comment. Math. Univ. Carolin. 36 (1995) 263-268
• Generalized domination in chordal graphs (with P. Manuel and M. Miller) Nordic Journal of Computing 2 (1995), 41-50
• Matchability of Hadamard Matrices (with J. Ne\v set\v ril and M. Rosenfeld) Proceedings Southeastern Conference on Combinatorics 1996, Congr. Numer. 117 (1996) 175-185
• Coloring precolored perfect graphs (with A. Sebo) Journal Graph Theory 25 (1997), 207-215
• Coloring and covering polygon-circle graphs (with A. Kostochka) Discrete Mathematics 163 (1997), 299-305
• Covers of regular graphs (with A.Proskurowski and J.A.Telle) Journal Combinatorial Theory Ser. B 71 (1997), 1-16
• On the computational complexity of (O,P)-partition problems, (with I. Schiermeyer), Discussiones Math. Graph Theory 17 (1997), 253-258
• Transversal partitioning in balanced hypergraphs (with E. Dahlhaus, P. Manuel and M. Miller) Discrete Math. 79 (1997), 75-89
• Graphs maximal with respect to hom-properties (with P. Mihok and G. Semanisin) Discussiones Math. Graph Theory 17 (1997), 77-88
• Computational complexity of the Krausz dimension of graphs (with P. Hlineny) In: Graph-Theoretic Concepts of Computer Science, Proceedings of 23rd International Workshop WG'97, Berlin, Germany, 1997, Lecture Notes in Computer Science 1335, Springer Verlag, Berlin Heidelberg, 1997, pp. 214-228
• Complexity of colored graph covers I. Colored directed multigraphs (with A.Proskurowski and J.A.Telle) In: Graph-Theoretic Concepts of Computer Science, Proceedings of 23rd International Workshop WG'97, Berlin, Germany, 1997, Lecture Notes in Computer Science 1335, Springer Verlag, Berlin Heidelberg, 1997, pp. 242-257.
• A note on intersection representations of co-planar graphs (with A. Kubena) Discrete Applied Mathematics 178 (1998) 251-255
• Brooks-type theorems for choosability with separation (with M. Voigt and Zs. Tuza) J. Graph Theory 27 (1998) 43-49
• Choosing sets of color sets (with M. Voigt and Zs. Tuza) Discrete Math. 191 (1998) 139-148
• Disjoint and Unfolding Domination in Graphs (with P. Manuel, M. Miller and A. Proskurowski) Australasian Journal of Combinatorics, 18 (1998), 277 - 292
• On the complexity of graph covering problems (with A.Proskurowski and J.A.Telle) Nordic Journal of Computing 5 (1998), 173-195
  • [conference version appeared as On the computational complexity of graph covering problems (with A. Proskurowski and J.A.Telle), In: Graph-Theoretic Concepts of Computer Science, Proceedings of 20th International Workshop WG'94, Munchen, Germany, June 1994, Lecture Notes in Computer Science 903, Springer Verlag, Berlin Heidelberg, 1995, pp. 93-105]
• Crossing number of abstract topological graphs In: Graph Drawing (S. Whitesides ed.), Proceedings Graph Drawing '98, Montreal, August 1998, Lecture Notes in Computer Science 1547, Springer Verlag, Berlin Heidelberg, 1998, pp. 238-245
• Graph Designs, Hadamard Matrices and Geometric Configurations (with J. Nesetril and M. Rosenfeld) In: Graph Theory and Combinatorial Biology (L.Lovasz, ed.), based on talks at International colloquium on combinatorics and graph theory, Balatonlelle, Hungary, July 1996, Bolyai Soc. Math. Stud. 7, 1999, pp. 101-123.
• Rankings of directed graphs (with Zs. Tuza) SIAM J. Discrete Math. 12 (1999), 374-384
  • [conference version published as Rankings of directed graphs (with Zs. Tuza) In: In: Graph-Theoretic Concepts in Computer Science, Proceedings of 24th International Workshop WG'98, Smolenice Castle, Slovakia, 1998, Lecture Notes in Computer Science 1517, Springer Verlag, Berlin Heidelberg, 1998, pp. 114-123]
• New trends in the theory of graph colorings: Choosability and list coloring, (with Zs. Tuza and M. Voigt) In: Contemporary Trends in Discrete Mathematics (from DIMACS and DIMATIA to the future) (eds. R.L.Graham, J.Kratochvil, J.Nesetril, F.S.Roberts), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 49, American Mathematical Society, Providence, RI, 1999, pp. 183-197
• Fixed-parameter complexity of $\lambda$-colorings (with J. Fiala and T. Kloks), In: Graph Theoretic Concepts in Computer Science (P. Widmayer, G.Neyer, S.Eidenbenz, eds.), Proceedings WG '99, Ascona, June 1999, Lecture Notes in Computer Science 1665, Springer Verlag, 1999, pp. 350-363
• Hom-properties are uniquely factorizable into irreducible factors (with P. Mihok) Discrete Math. 213 (2000) 189-194
• Independent sets with domination constraints, (with M. Halldorsson and J.A. Telle), Discrete Appl. Math. 99 (2000) 39-54
  • [conference version published as Independent sets with domination constraints (extended abstract), (with M.Halldorsson and J.A Telle), Proceedings ICALP'98 - 25th International Colloquium on Automata, Languages and Programming, Aalborg, Denmark, July 13-17 1998, LNCS vol. 1443, pp. 176-187]
• Mod-2 Independence and Domination in Graphs (with Halldorsson and J.A.Telle) Internat. J. Found. Comput. Sci. 11 (2000) 355-363
  • [based on conference paper Mod-2 Independence and Domination in Graphs (with Halldorsson and J.A.Telle), In: Graph Theoretic Concepts in Computer Science (P. Widmayer, G.Neyer, S.Eidenbenz, eds.), Proceedings WG '99, Ascona, June 1999, Lecture Notes in Computer Science 1665, Springer Verlag, 1999, pp. 101-109]
• Representing graphs by disks and balls (a survey of recognition-complexity results) (with P. Hlin\v en\'y) Discrete Math 229 (2001) 101-124
  • [partly based on conference paper Intersection graphs of noncrossing arc-connected sets in the plane In: Graph Drawing (F.J.Brandenburg ed.), Proceedings Graph Drawing '96, Berkeley, September 1996, Lecture Notes in Computer Science 1190, Springer Verlag, Berlin Heidelberg, 1997, pp. 257-270 ]
• Efficient algorithms for graphs with few $P_4$s, (with L. Babel, T. Kloks, D. Kratsch, H. Muller and S. Olariu), Discrete Mathematics 235 (2001) 29-51
• Fixed-parameter complexity of $\lambda$-labelings (with J. Fiala and T. Kloks), Discrete Applied Math. 113 (2001), 59-72
  • [based on conference paper Fixed-parameter complexity of $\lambda$-colorings (with J. Fiala and T. Kloks), In: Graph Theoretic Concepts in Computer Science (P. Widmayer, G.Neyer, S.Eidenbenz, eds.), Proceedings WG '99, Ascona, June 1999, Lecture Notes in Computer Science 1665, Springer Verlag, 1999, pp. 350-363]
• Complexity of coloring graphs without forbidden induced subgraphs (with D. Kral, Zs. Tuza and G. Woeginger) In: Graph Theoretic Concepts in Computer Science, Proceedings WG '01, Boltenhagen, June 2001, Lecture Notes in Computer Science 2204, Springer Verlag, 2001, pp. 254-262
• Complexity note on mixed hypergraphs (with D. Kral and H.J. Voss) In: Mathematical Foundations of Computer Science 2001 (J.Sgall, A.Pultr, P.Kolman eds.), Proceedings MFCS 2001, Lecture Notes in Computer Science 2136, Springer Verlag, 2001, pp. 474-485
• Distance constrained labelings of precolored trees (with J. Fiala and A.Proskurowski), Theoretical Computer Science (A. Restivo, S. Ronchi Della Rocca, L. Roversi, eds.) Proceedings 7th Italian Conference, ICTCS 2001, Torino, October 2001, Lecture Notes in Computer Science 2202, Springer Verlag, 2001, pp. 285-292
• Complexity of partial covers of graphs (with J. Fiala), In: Algorithms and Computation (P.Eades and T.Takaoka, eds.), Proceedings ISAAC 2001, Christchurch, December 2001, Lecture Notes in Computer Science 2223, Springer Verlag, Berlin Heidelberg 2001, pp. 537-549
• Sum graph labels - An upper bound and related problems (with M.Miller and H.M.Nguyen), in: Proceedings AWOCA 2001 (E. Baskoro, ed.), Institut Teknologi Bandung, Indonesia, 2001, p. 126-131
• Partial covers of graphs,(with J. Fiala) Discussiones Mathematicae Graph Theory 22 (2002) 89-99
• On the complexity of bicoloring clique hypergraphs of graphs, (with Zs. Tuza), J of Algorithms 45 (2002) 40-54
  • [extended abstract published as Bicoloring clique hypergraphs (with Zs. Tuza), In: Proceedings of 11th annual ACM symposium on Discrete Algorithms SODA '00, San Francisco, January 2000, ACM and SIAM, 2000, pp. 40-41]
• On the injective chromatic number of graphs, (with G. Hahn, J. Siran and D. Sotteau), Discr. Math. 256 (2002) 179-192
• On the b-chromatic number of graphs (with Zs. Tuiza and M. Voigt), In: Graph Theoretic Concepts in Computer Science (L. Kucera, ed.), Proceedings WG '02, Cesky Krumlov, June 2002, Lecture Notes in Computer Science 2573, Springer Verlag, 2002, pp. 310-320
• Geometric systems of disjoint representatives (with J. Fiala and A. Proskurowski), in: Graph Drawing (M.T.Goodrich, S.G.Kobourov, eds.), Proceedings 10th International Symposium GD 2002, Irvine, August 2002, Lecture Notes in Computer Science 2528, Springer Verlag, 2002, pp. 110-117
• Mixed hypergraphs with bounded degree: Edge-coloring of mixed multigraphs, (with D. Kral and H.J.Voss), Theoret. Comput. Sci. 295 (2003) 263-278
• Complexity of hypergraph coloring and Seidel's switching, in: Graph Theoretic Concepts in Computer Science (H. Bodlaender, ed.), Proceedings WG 2003, Elspeet, June 2003, Lecture Notes in Computer Science 2880, Springer Verlag, 2003, pp. 297-308
• Two results on intersection graphs of polygons (with M. Pergel), in: Graph Drawing (G. Liotta, ed.), Proceedings 11th International Symposium GD 2003, Perugia, Italy, September 2003, Lecture Notes in Computer Science 2912, Springer Verlag, 2004, pp. 59-70
• Mixed hypercacti (with D. Kral and H.J. Voss), Discr. Math. 286(1-2) (2004), 99-113
• Edge decompositions of multigraphs into multi-2-paths (with Z. Lonc, M. Meszka, Z. Skupie\'n), Opuscula Math. 24 (2004) 97-102
• Elegant distance constrained labelings of trees (with J. Fiala and P.A. Golovach), in: Graph-Theoretic Concepts in Computer Science (J. Hromkovic, M. Nagl, B. Westfechtel, eds.), Proceedings WG'04, Bad Honnef, Germany, June 2004, Lecture Notes in Computer Science 3353, Springer Verlag, 2004, pp. 58-67
• Computing the branchwidth of interval graphs (with T. Kloks and H. Muller), Discr. Appl. Math. 145 (2005) 266-275
  • [based on conference paper New branchwidth territories (with T. Kloks and H. Muller), In: STACS 99 (Ch. Meinel, ed.) Proceedings 16th symposium on Theoretical aspects of computer science, Trier, March 1999, Lecture Notes in Computer Science 1563, Springer Verlag, 1999, pp. 173-183]
• Systems of distant representatives (with J. Fiala and A. Proskurowski), Discr. Appl. Math. 145 (2005) 306-316
• On the computational complexity of partial covers of Theta graphs (Extended Abstract) (with J. Fiala and A. Por), in: Electronic Notes in Discr. Math. 19 (P. Feofiloff, C. de Figueiredo, Y. Wakabayashi, eds.), Proceedings GRACO 2005, Elsevier, 2005, pp. 79-85
• Distance constrained labelings of graphs of bounded treewidth (with J. Fiala and P. Golovach), in: Automata, Languages and Programming, (L. Caires, G.F. Italiano, L. Monteiro, C. Palamidessi and M. Yung, eds.), Proceedings ICALP 2005, Lecture Notes in Computer Science 3580, Springer 2005 pp. 360-372
• On the computational complexity of the L(2,1)-labeling problem for regular graphs (with J. Fiala), in: Theoretical Computer Science (M. Coppo, E. Lodi, G. Michele Pinna, eds.), Proceedings 9th Italian Conference ICTCS 2005, Siena, Italy, October 2005, Lecture Notes in Computer Science 3701, Springer 2005, pp. 228-236
• Coloring mixed hypertrees (with D. Kral, A. Proskurowski and H.-J. Voss), Discr. Appl. Math. 154 (2006) 660-672
  • [based on conference version Coloring mixed hypertrees (with D. Kral, A. Proskurowski and H.J. Voss), In: Graph Theoretic Concepts in Computer Science, Proceedings WG '00, Konstanz, June 2000, Lecture Notes in Computer Science 1928, Springer Verlag, 2000, pp. 279-289]
• Planar graph coloring avoiding monochromatic subgraphs: Trees and paths make it difficult (with H. Broersma, F.V. Fomin, and G. Woeginger) Algorithmica 44 (2006) 343-361
  • [extended abstract published as Planar graph coloring with forbidden subgraphs: Why trees and paths are dangerous (with H. Broersma, F.V. Fomin and G.J. Woeginger), in: Algorithm Theory - SWAT 2002 (M. Penttonen, E. M. Schmidt, eds.), Proceedings 8th Scandinavian Workshop on Algorithm Theory, Turku, July 2002, Lecture Notes in Computer Science 2368, Springer Verlag, Berlin Heidelberg 2002, pp. 160-169]
• Max-Tolerance graphs as intersection graphs: Cliques, cycles and recognition (with M. Kaufmann, K. A. Lehmann and A. R. Subramanian), in: Proceedings SODA '06, ACM-SIAM 2006, 832-841
• Fixed parameter tractability of Independent set in segment intersection graphs, in: Parametrized and exact Computation, Proceedings of IWPEC 2006 (H. Bodlaender, M. Langston, eds.), LNCS 4169, 2006, pp. 166-174
• Locally injective graph homomorphisms: Lists guarantee dichotomy (with J. Fiala), in: Graph-Theoretic Concepts in Computer Science, Proceedings WG 2006 (F. Fomin, ed.), LNCS 4271, Springer Verlag, 2006, pp. 15-26
• On the Complexity of the Balanced Vertex Ordering Problem (with J. Kara and D. Wood), DMTCS 9 (2007) 1-12
  • [conference version published as On the complexity of the balanced vertex ordering problem in: Computing and Combinatorics (Lusheng Wang ed.), Proceedings 11th Annual International Conference on Computing and Combinatorics COCOON 2005, Kunming, China, August 2005, Lecture Notes in Computer Science 3595, Springer 2005, pp. 849-858]
• Geometric intersection graphs: Do short cycles help? (Extended abstract) (with M. Pergel), in: Computing and Combinatorics, Proceedings COCOON 2007 (G. Lin, ed.), LNCS 4598, Springer Verlag, 2007, pp. 118-128
• Branch and recharge: Exact algorithms for generalized domination (with F. Fomin, P. Golovach, D. Kratsch and M. Liedloff) in: Algorithms and Data Structures, Proceedings WADS 2007 (F. Dehne, J. R. Sack, N. Zeh, eds.) LNCS 4619, Springer Verlag, 2007, pp. 508-519
• Exact algorithms for L(2,1)-labeling of graphs (with D. Kratsch and M. Liedloff) in: Mathematical Foundations of Computer Science 2007, Proceedings MFCS 2007 (L. Kucera and A. Kucera, eds.) LNCS 4708, Springer Verlag, 2007, pp. 513-524
• Homothetic Triangle Contact Representations of Planar Graphs (with M. Badent, C. Binucci, E. Di Giacomo, W. Didimo, S. Felsner, F. Giordano, P. Palladino, M. Patrignani, F. Trotta) Proceedings of the 19th Annual Canadian Conference on Computational Geometry, CCCG 2007 (P. Bose, ed.), Carleton University, Ottawa, Canada 2007, ISBN 978-0-7709-0520-0, pp. 233-236
• Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs (with Petr Golovach), in: Graph-Theoretic Concepts in Computer Science, Proceedings WG 2007 (A. Brandstaedt, D. Kratsch and H. Muller, eds.) LNCS 4769 Springer Verlag 2007, pp. 1-11
• Clustered Planarity: Small Clusters in Eulerian Graphs (with E. Jelinkova, J. Kara, M. Pergel, O. Suchy and T. Vyskocil), in: Graph Drawing (s.-H. Hong, T. Nishizeki, eds.), Proceedings GD 2007, LNCS 4875, Springer Verlag, 2008, pp. 303-314
• Moving Vertices to Make Drawings Plane (with Xavier Goaoc, Yoshio Okamoto, Chan-Su Shin, and Alexander Wolff) in: Graph Drawing (s.-H. Hong, T. Nishizeki, eds.), Proceedings GD 2007, LNCS 4875, Springer Verlag, 2008, pp. 101-112