| * | 2009 |
|---|
| 101 | EE | Jirí Fiala,
Petr A. Golovach,
Jan Kratochvíl:
Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover.
TAMC 2009: 221-230 |
| 100 | EE | Jan Kratochvíl,
Andrzej Proskurowski,
Oriol Serra:
Guest editors' foreword.
Discrete Applied Mathematics 157(12): 2575-2576 (2009) |
| 99 | EE | 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) |
| 2008 |
|---|
| 98 | EE | 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 |
| 97 | EE | 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 |
| 96 | EE | Eva Jelínková,
Jan Kratochvíl:
On Switching to H-Free Graphs.
ICGT 2008: 379-395 |
| 95 | EE | Fedor V. Fomin,
Petr A. Golovach,
Jan Kratochvíl:
On tractability of Cops and Robbers game.
IFIP TCS 2008: 171-185 |
| 94 | EE | 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 |
| 93 | EE | Jirí Fiala,
Petr A. Golovach,
Jan Kratochvíl:
Distance Constrained Labelings of Trees.
TAMC 2008: 125-135 |
| 92 | EE | Petr A. Golovach,
Jan Kratochvíl:
Generalized Domination in Degenerate Graphs: A Complete Dichotomy of Computational Complexity.
TAMC 2008: 182-191 |
| 91 | EE | Jirí Fiala,
Jan Kratochvíl:
Locally constrained graph homomorphisms - structure, complexity, and applications.
Computer Science Review 2(2): 97-111 (2008) |
| 90 | EE | 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) |
| 89 | EE | Jan Kratochvíl,
Martin Pergel:
Intersection graphs of homothetic polygons.
Electronic Notes in Discrete Mathematics 31: 277-280 (2008) |
| 2007 |
|---|
| 88 | | 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 |
| 87 | EE | Jan Kratochvíl,
Martin Pergel:
Geometric Intersection Graphs: Do Short Cycles Help?
COCOON 2007: 118-128 |
| 86 | EE | Xavier Goaoc,
Jan Kratochvíl,
Yoshio Okamoto,
Chan-Su Shin,
Alexander Wolff:
Moving Vertices to Make Drawings Plane.
Graph Drawing 2007: 101-112 |
| 85 | EE | 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 |
| 84 | EE | Jan Kratochvíl,
Dieter Kratsch,
Mathieu Liedloff:
Exact Algorithms for L (2, 1)-Labeling of Graphs.
MFCS 2007: 513-524 |
| 83 | EE | 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 |
| 82 | EE | Petr A. Golovach,
Jan Kratochvíl:
Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs.
WG 2007: 1-11 |
| 81 | EE | Xavier Goaoc,
Jan Kratochvíl,
Yoshio Okamoto,
Chan-Su Shin,
Alexander Wolff:
Moving Vertices to Make Drawings Plane
CoRR abs/0706.1002: (2007) |
| 80 | EE | Jan Kratochvíl,
Josep Díaz,
Jirí Fiala:
Editorial.
Discrete Applied Mathematics 155(2): 79-80 (2007) |
| 79 | EE | 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) |
| 78 | EE | Petr Hlinený,
Jan Kratochvíl,
Roman Nedela,
Martin Skoviera:
Preface.
Electronic Notes in Discrete Mathematics 28: 1 (2007) |
| 2006 |
|---|
| 77 | EE | Jan Kára,
Jan Kratochvíl:
Fixed Parameter Tractability of Independent Set in Segment Intersection Graphs.
IWPEC 2006: 166-174 |
| 76 | EE | 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 |
| 75 | EE | Jirí Fiala,
Jan Kratochvíl:
Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy.
WG 2006: 15-26 |
| 74 | EE | 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) |
| 73 | EE | Daniel Král,
Jan Kratochvíl,
Andrzej Proskurowski,
Heinz-Jürgen Voss:
Coloring mixed hypertrees.
Discrete Applied Mathematics 154(4): 660-672 (2006) |
| 2005 |
|---|
| 72 | EE | Jan Kára,
Jan Kratochvíl,
David R. Wood:
On the Complexity of the Balanced Vertex Ordering Problem.
COCOON 2005: 849-858 |
| 71 | EE | Jirí Fiala,
Petr A. Golovach,
Jan Kratochvíl:
Distance Constrained Labelings of Graphs of Bounded Treewidth.
ICALP 2005: 360-372 |
| 70 | EE | Jirí Fiala,
Jan Kratochvíl:
On the Computational Complexity of the L(2, 1)-Labeling Problem for Regular Graphs.
ICTCS 2005: 228-236 |
| 69 | EE | Jan Kratochvíl,
Andrzej Proskurowski,
Oriol Serra:
Structural decompositions, width parameters, and graph labelings.
Discrete Applied Mathematics 145(2): 141-142 (2005) |
| 68 | EE | Ton Kloks,
Jan Kratochvíl,
Haiko Müller:
Computing the branchwidth of interval graphs.
Discrete Applied Mathematics 145(2): 266-275 (2005) |
| 67 | EE | Jirí Fiala,
Jan Kratochvíl,
Andrzej Proskurowski:
Systems of distant representatives.
Discrete Applied Mathematics 145(2): 306-316 (2005) |
| 66 | EE | 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) |
| 65 | EE | Václav Koubek,
Jan Kratochvíl:
Preface.
Theor. Comput. Sci. 345(2-3): 171-172 (2005) |
| 2004 |
|---|
| 64 | | Jirí Fiala,
Václav Koubek,
Jan Kratochvíl:
Mathematical Foundations of Computer Science 2004, 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004, Proceedings
Springer 2004 |
| 63 | EE | Jirí Fiala,
Petr A. Golovach,
Jan Kratochvíl:
Elegant Distance Constrained Labelings of Trees.
WG 2004: 58-67 |
| 62 | EE | Daniel Král,
Jan Kratochvíl,
Heinz-Jürgen Voss:
Mixed hypercacti.
Discrete Mathematics 286(1-2): 99-113 (2004) |
| 2003 |
|---|
| 61 | EE | Jan Kratochvíl,
Martin Pergel:
Two Results on Intersection Graphs of Polygons.
Graph Drawing 2003: 59-70 |
| 60 | EE | Jan Kratochvíl:
Complexity of Hypergraph Coloring and Seidel's Switching.
WG 2003: 297-308 |
| 59 | EE | 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) |
| 2002 |
|---|
| 58 | EE | Jirí Fiala,
Jan Kratochvíl,
Andrzej Proskurowski:
Geometric Systems of Disjoint Representatives.
Graph Drawing 2002: 110-117 |
| 57 | EE | 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 |
| 56 | EE | Jan Kratochvíl,
Zsolt Tuza,
Margit Voigt:
On the b-Chromatic Number of Graphs.
WG 2002: 310-320 |
| 55 | EE | 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) |
| 54 | EE | Jan Kratochvíl,
Zsolt Tuza:
On the complexity of bicoloring clique hypergraphs of graphs.
J. Algorithms 45(1): 40-54 (2002) |
| 53 | EE | Hubert de Fraysseix,
Jan Kratochvíl:
Guest Editors' Foreword.
J. Graph Algorithms Appl. 6(1): 3-5 (2002) |
| 2001 |
|---|
| 52 | EE | Jirí Fiala,
Jan Kratochvíl,
Andrzej Proskurowski:
Distance Constrained Labeling of Precolored Trees.
ICTCS 2001: 285-292 |
| 51 | EE | Jirí Fiala,
Jan Kratochvíl:
Complexity of Partial Covers of Graphs.
ISAAC 2001: 537-549 |
| 50 | EE | Daniel Král,
Jan Kratochvíl,
Heinz-Jürgen Voss:
Complexity Note on Mixed Hypergraphs.
MFCS 2001: 474-486 |
| 49 | EE | Daniel Král,
Jan Kratochvíl,
Zsolt Tuza,
Gerhard J. Woeginger:
Complexity of Coloring Graphs without Forbidden Induced Subgraphs.
WG 2001: 254-262 |
| 48 | | Jirí Fiala,
Ton Kloks,
Jan Kratochvíl:
Fixed-parameter complexity of lambda-labelings.
Discrete Applied Mathematics 113(1): 59-72 (2001) |
| 47 | EE | 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) |
| 46 | EE | 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) |
| 45 | EE | Miroslav Fiedler,
Jan Kratochvíl,
Jaroslav Nesetril:
Foreword.
Discrete Mathematics 233(1-3): 1-2 (2001) |
| 44 | EE | Luitpold Babel,
Ton Kloks,
Jan Kratochvíl,
Dieter Kratsch,
Haiko Müller,
Stephan Olariu:
Efficient algorithms for graphs with few P4's.
Discrete Mathematics 235(1-3): 29-51 (2001) |
| 2000 |
|---|
| 43 | EE | Jan Kratochvíl,
Zsolt Tuza:
On the complexity of bicoloring clique hypergraphs of graphs (extended abstract).
SODA 2000: 40-41 |
| 42 | EE | Daniel Král,
Jan Kratochvíl,
Andrzej Proskurowski,
Heinz-Jürgen Voss:
Coloring Mixed Hypertrees.
WG 2000: 279-289 |
| 41 | EE | 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) |
| 40 | EE | Jan Kratochvíl,
Peter Mihók:
Hom-properties are uniquely factorizable into irreducible factors.
Discrete Mathematics 213(1-3): 189-194 (2000) |
| 39 | | 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) |
| 1999 |
|---|
| 38 | | Jan Kratochvíl:
Graph Drawing, 7th International Symposium, GD'99, Stirín Castle, Czech Republic, September 1999, Proceedings
Springer 1999 |
| 37 | EE | Ton Kloks,
Jan Kratochvíl,
Haiko Müller:
New Branchwidth Territories.
STACS 1999: 173-183 |
| 36 | EE | Magnús M. Halldórsson,
Jan Kratochvíl,
Jan Arne Telle:
Mod-2 Independence and Domination in Graphs.
WG 1999: 101-109 |
| 35 | EE | Jirí Fiala,
Ton Kloks,
Jan Kratochvíl:
Fixed-Parameter Complexity of lambda-Labelings.
WG 1999: 350-363 |
| 34 | EE | Jan Kratochvíl,
Zsolt Tuza:
Rankings of Directed Graphs.
SIAM J. Discrete Math. 12(3): 374-384 (1999) |
| 1998 |
|---|
| 33 | EE | Jan Kratochvíl:
Crossing Number of Abstract Topological Graphs.
Graph Drawing 1998: 238-245 |
| 32 | EE | Magnús M. Halldórsson,
Jan Kratochvíl,
Jan Arne Telle:
Independent Sets with Domination Constraints.
ICALP 1998: 176-187 |
| 31 | EE | Jan Kratochvíl,
Zsolt Tuza:
Rankings of Directed Graphs.
WG 1998: 114-123 |
| 30 | EE | Jan Kratochvíl,
Ales Kubena:
On intersection representations of co-planar graphs.
Discrete Mathematics 178(1-3): 251-255 (1998) |
| 29 | EE | Jan Kratochvíl,
Zsolt Tuza,
Margit Voigt:
Complexity of choosing subsets from color sets.
Discrete Mathematics 191(1-3): 139-148 (1998) |
| 28 | | Jan Kratochvíl,
Andrzej Proskurowski,
Jan Arne Telle:
On the Complexity of Graph Covering Problems.
Nord. J. Comput. 5(3): 173-195 (1998) |
| 1997 |
|---|
| 27 | EE | Petr Hlinený,
Jan Kratochvíl:
Computational Complexity of the Krausz Dimension of Graphs.
WG 1997: 214-228 |
| 26 | EE | Jan Kratochvíl,
Andrzej Proskurowski,
Jan Arne Telle:
Complexity of Colored Graph Covers I. Colored Directed Multigraphs.
WG 1997: 242-257 |
| 25 | EE | Elias Dahlhaus,
Jan Kratochvíl,
Paul D. Manuel,
Mirka Miller:
Transversal Partitioning in Balanced Hypergraphs.
Discrete Applied Mathematics 79(1-3): 75-89 (1997) |
| 24 | EE | Alexandr V. Kostochka,
Jan Kratochvíl:
Covering and coloring polygon-circle graphs.
Discrete Mathematics 163(1-3): 299-305 (1997) |
| 23 | EE | Jan Kratochvíl,
Andrzej Proskurowski,
Jan Arne Telle:
Covering Regular Graphs.
J. Comb. Theory, Ser. B 71(1): 1-16 (1997) |
| 1996 |
|---|
| 22 | | Jan Kratochvíl:
Intersection Graphs of Noncrossing Arc-Connected Sets in the Plane.
Graph Drawing 1996: 257-270 |
| 1995 |
|---|
| 21 | | Jan Kratochvíl,
Teresa M. Przytycka:
Grid Intersection and Box Intersection Graphs on Surfaces (Extended Abstract).
Graph Drawing 1995: 365-372 |
| 20 | | Michael R. Fellows,
Jan Kratochvíl,
Martin Middendorf,
Frank Pfeiffer:
The Complexity of Induced Minors and Related Problems.
Algorithmica 13(3): 266-282 (1995) |
| 19 | | Jan Kratochvíl,
Paul D. Manuel,
Mirka Miller:
Generalized Domination in Chordal Graphs.
Nord. J. Comput. 2(1): 41-50 (1995) |
| 1994 |
|---|
| 18 | EE | Jan Kratochvíl,
Andrzej Proskurowski,
Jan Arne Telle:
Complexity of Graph Covering Problems.
WG 1994: 93-105 |
| 17 | | Jan Kratochvíl,
Zsolt Tuza:
Algorithmic complexity of list colorings.
Discrete Applied Mathematics 50(3): 297-302 (1994) |
| 16 | EE | Jan Kratochvíl:
A Special Planar Satisfiability Problem and a Consequence of Its NP-completeness.
Discrete Applied Mathematics 52(3): 233-252 (1994) |
| 15 | EE | Jan Kratochvíl:
Regular codes in regular graphs are difficult.
Discrete Mathematics 133(1-3): 191-205 (1994) |
| 14 | EE | Jan Kratochvíl,
Jirí Matousek:
Intersection Graphs of Segments.
J. Comb. Theory, Ser. B 62(2): 289-315 (1994) |
| 1993 |
|---|
| 13 | | Jan Kratochvíl,
Mirko Krivánek:
Satisfiability of Co-Nested Formulas.
Acta Inf. 30(4): 397-403 (1993) |
| 12 | | 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) |
| 1992 |
|---|
| 11 | EE | Jan Kratochvíl,
Svatopluk Poljak:
Compatible 2-factors.
Discrete Applied Mathematics 36(3): 253-266 (1992) |
| 10 | EE | Svante Janson,
Jan Kratochvíl:
Thresholds for classes of intersection graphs.
Discrete Mathematics 108(1-3): 307-326 (1992) |
| 1991 |
|---|
| 9 | | Michael R. Fellows,
Jan Kratochvíl,
Matthias Middendorf,
Frank Pfeiffer:
Induced minors and related problems.
Graph Structure Theory 1991: 179-182 |
| 8 | EE | Jan Kratochvíl:
String graphs. I. The number of critical nonstring graphs is infinite.
J. Comb. Theory, Ser. B 52(1): 53-66 (1991) |
| 7 | EE | Jan Kratochvíl:
String graphs. II. recognizing string graphs is NP-hard.
J. Comb. Theory, Ser. B 52(1): 67-78 (1991) |
| 6 | EE | Jan Kratochvíl,
Jirí Matousek:
String graphs requiring exponential representations.
J. Comb. Theory, Ser. B 53(1): 1-4 (1991) |
| 5 | | Svante Janson,
Jan Kratochvíl:
Proportional Graphs.
Random Struct. Algorithms 2(2): 209-224 (1991) |
| 4 | | Jan Kratochvíl,
Anna Lubiw,
Jaroslav Nesetril:
Noncrossing Subgraphs in Topological Layouts.
SIAM J. Discrete Math. 4(2): 223-244 (1991) |
| 1988 |
|---|
| 3 | EE | Jan Kratochvíl,
Mirko Krivánek:
On the Computational Complexity of Codes in Graphs.
MFCS 1988: 396-404 |
| 2 | | Pavol Hell,
David G. Kirkpatrick,
Jan Kratochvíl,
Igor Kríz:
On Restricted Two-Factors.
SIAM J. Discrete Math. 1(4): 472-484 (1988) |
| 1986 |
|---|
| 1 | EE | Jan Kratochvíl:
Perfect codes over graphs.
J. Comb. Theory, Ser. B 40(2): 224-228 (1986) |
