×
Author ID: kratochvil.jan Recent zbMATH articles by "Kratochvíl, Jan"
Published as: Kratochvíl, Jan; Kratochvil, Jan; Kratochvíl, J.; Kratochvil, J.; Kratochvíl
Homepage: https://kam.mff.cuni.cz/~honza/
External Links: MGP · ORCID · Wikidata · ResearchGate · dblp · GND · IdRef · theses.fr
all top 5

Co-Authors

17 single-authored
33 Fiala, Jiří
16 Golovach, Petr A.
15 Klavík, Pavel
13 Jelínek, Vít
13 Proskurowski, Andrzej
13 Telle, Jan Arne
13 Vyskočil, Tomáš
12 Tuza, Zsolt
11 Rutter, Ignaz
10 Nešetřil, Jaroslav
9 Jelínková, Eva
9 Liedloff, Mathieu
8 Fomin, Fedor V.
7 Gavenčiak, Tomáš
7 Miller, Mirka
7 Pergel, Martin
7 Rzążewski, Paweł
6 Junosza-Szaniawski, Konstanty
6 Král’, Daniel
6 Kratsch, Dieter
5 Jedličková, Nikola
5 Kára, Jan
5 Kloks, Ton
5 Matoušek, Jiří
5 Montecchiani, Fabrizio
5 Otachi, Yota
5 Saitoh, Toshiki
5 Suchý, Ondřej
5 Valtr, Pavel
5 Voss, Heinz-Jürgen
4 Angelini, Patrizio
4 Chaplick, Steven
4 Halldórsson, Magnús Mar
4 Hliněný, Petr
4 Lidický, Bernard
4 Lipp, Fabian
4 Nedela, Roman
4 Tesař, Marek
4 Voigt, Margit
3 Bok, Jan
3 Di Battista, Giuseppe
3 Fiedler, Miroslav
3 Heggernes, Pinar
3 Kaufmann, Michael
3 Manuel, Paul D.
3 Müller, Haiko
3 Raftopoulou, Chrysanthi N.
3 Woeginger, Gerhard
2 Abello, James M.
2 Binucci, Carla
2 Broersma, Hajo J.
2 Chimani, Markus
2 Da Lozzo, Giordano
2 Didimo, Walter
2 Fellows, Michael Ralph
2 Frati, Fabrizio
2 Goaoc, Xavier
2 Gordinowicz, Przemysław
2 Grilli, Luca
2 Gronemann, Martin
2 Hahn, Gena
2 Hell, Pavol
2 Hong, Seok-Hee
2 Janson, Svante
2 Kindermann, Philipp
2 Klazar, Martin
2 Klein, Karsten
2 Knop, Dušan
2 Kobourov, Stephen G.
2 Kolman, Petr
2 Koubek, Vaclav
2 Koutecký, Martin
2 Křivánek, Mirko
2 Li, Angsheng
2 Lokshtanov, Daniel
2 Mancini, Federico
2 Masařík, Tomáš
2 Middendorf, Matthias
2 Mihók, Peter
2 Novotná, Jana
2 Okamoto, Yoshio
2 Patrignani, Maurizio
2 Pfeiffer, Frank
2 Pór, Attila
2 Rosenfeld, Moshe
2 Rossmanith, Peter
2 Saumell, Maria
2 Seifrtová, Michaela
2 Shin, Chan-Su
2 Talon, Alexandre
2 Tollis, Ioannis G.
2 Wolff, Alexander
2 Wood, David Ronald
2 Zeps, Dainis A.
1 Axhausen, Kay W.
1 Babel, Luitpold
1 Bathe, Klaus-Jürgen
1 Bekos, Michael A.
1 Bonato, Anthony
1 Brimkov, Valentin E.
...and 93 more Co-Authors

Publications by Year

Citations contained in zbMATH Open

163 Publications have been cited 2,091 times in 1,443 Documents Cited by Year
Complexity of coloring graphs without forbidden induced subgraphs. Zbl 1042.68639
Král’, Daniel; Kratochvíl, Jan; Tuza, Zsolt; Woeginger, Gerhard J.
104
2001
A special planar satisfiability problem and a consequence of its NP- completeness. Zbl 0810.68083
Kratochvíl, Jan
85
1994
On the injective chromatic number of graphs. Zbl 1007.05046
Hahn, Geňa; Kratochvíl, Jan; Širáň, Jozef; Sotteau, Dominique
85
2002
On the \(b\)-chromatic number of graphs. Zbl 1024.05026
Kratochvíl, Jan; Tuza, Zsolt; Voigt, Margit
73
2002
Fixed-parameter complexity of \(\lambda\)-labelings. Zbl 0982.05085
Fiala, Jiří; Kloks, Ton; Kratochvíl, Jan
62
2001
Intersection graphs of segments. Zbl 0808.68075
Kratochvíl, Jan; Matoušek, Jiří
61
1994
String graphs. II: Recognizing string graphs is NP-hard. Zbl 0661.05054
Kratochvíl, Jan
55
1991
On the computation of the hull number of a graph. Zbl 1215.05184
Dourado, Mitre C.; Gimbel, John G.; Kratochvíl, Jan; Protti, Fábio; Szwarcfiter, Jayme L.
53
2009
Covering and coloring polygon-circle graphs. Zbl 0871.05025
Kostochka, Alexandr; Kratochvíl, Jan
50
1997
Perfect codes over graphs. Zbl 0563.94017
Kratochvíl, Jan
44
1986
Parameterized complexity of coloring problems: treewidth versus vertex cover. Zbl 1216.68127
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
36
2011
Pursuing a fast robber on a graph. Zbl 1192.91027
Fomin, Fedor V.; Golovach, Petr A.; Kratochvíl, Jan; Nisse, Nicolas; Suchan, Karol
36
2010
On the complexity of bicoloring clique hypergraphs of graphs. Zbl 1030.68066
Kratochvíl, Jan; Tuza, Zsolt
36
2002
String graphs requiring exponential representations. Zbl 0675.05059
Kratochvíl, Jan; Matoušek, Jiří
35
1991
The capture time of a graph. Zbl 1177.91056
Bonato, A.; Golovach, P.; Hahn, G.; Kratochvíl, J.
34
2009
INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs. Zbl 0727.05056
Kratochvíl, Jan; Nešetřil, Jaroslav
33
1990
Precoloring extension with fixed color bound. Zbl 0821.05027
Kratochvíl, J.
31
1993
The complexity of induced minors and related problems. Zbl 0816.68070
Fellows, M. R.; Kratochvíl, J.; Middendorf, M.; Pfeiffer, F.
30
1995
Locally constrained graph homomorphisms – structure, complexity, and applications. Zbl 1302.05122
Fiala, Jiří; Kratochvíl, Jan
28
2008
Testing planarity of partially embedded graphs. Zbl 1398.68385
Angelini, Patrizio; Di Battista, Giuseppe; Frati, Fabrizio; Jelínek, Vít; Kratochvíl, Jan; Patrignani, Maurizio; Rutter, Ignaz
28
2015
Partial covers of graphs. Zbl 1017.05094
Fiala, Jiří; Kratochvíl, Jan
26
2002
New trends in the theory of graph colorings: Choosability and list coloring. Zbl 1025.05030
Kratochvíl, Jan; Tuza, Zsolt; Voigt, Margit
25
1999
Covering regular graphs. Zbl 0895.05049
Kratochvíl, Jan; Proskurowski, Andrzej; Telle, Jan Arne
25
1997
Representing graphs by disks and balls (a survey of recognition-complexity results). Zbl 0969.68118
Hliněný, Petr; Kratochvíl, Jan
25
2001
Distance constrained labelings of graphs of bounded treewidth. Zbl 1082.68080
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
25
2005
String graphs. I: The number of critical nonstring graphs is infinite. Zbl 0675.05058
Kratochvil, Jan
24
1991
Cluster vertex deletion: a parameterization between vertex cover and clique-width. Zbl 1365.68278
Doucha, Martin; Kratochvíl, Jan
23
2012
One more occurrence of variables makes satisfiability jump from trivial to NP-complete. Zbl 0767.68057
Kratochvíl, Jan; Savický, Petr; Tuza, Zsolt
22
1993
Systems of distant representatives. Zbl 1084.05059
Fiala, Jiří; Kratochvíl, Jan; Proskurowski, Andrzej
22
2005
Noncrossing subgraphs in topological layouts. Zbl 0731.68047
Kratochvíl, Jan; Lubiw, Anna; Nešetřil, Jaroslav
22
1991
Algorithmic complexity of list colorings. Zbl 0807.68055
Kratochvíl, Jan; Tuza, Zsolt
22
1994
Independent sets with domination constraints. Zbl 0939.05063
Halldórsson, Magnús M.; Kratochvíl, Jan; Telle, Jan Arne
21
2000
On restricted two-factors. Zbl 0672.05065
Hell, Pavol; Kirkpatrick, David; Kratochvíl, Jan; Kříž, Igor
20
1988
Complexity of graph covering problems. Zbl 0911.68076
Kratochvíl, Jan; Proskurowski, Andrzej; Telle, Jan Arne
20
1998
Contact representations of planar graphs: extending a partial representation is hard. Zbl 1417.05133
Chaplick, Steven; Dorbec, Paul; Kratochvíl, Jan; Montassier, Mickael; Stacho, Juraj
19
2014
A Kuratowski-type theorem for planarity of partially embedded graphs. Zbl 1259.05044
Jelínek, Vít; Kratochvíl, Jan; Rutter, Ignaz
18
2013
Brooks-type theorems for choosability with separation. Zbl 0894.05016
Kratochvíl, J.; Tuza, Zsolt; Voigt, Margit
17
1998
Fixed-parameter complexity of \(\lambda\)-labelings. Zbl 0943.05072
Fiala, Jiří; Kloks, Ton; Kratochvíl, Jan
16
1999
Exact algorithms for \(L(2,1)\)-labeling of graphs. Zbl 1213.68455
Havet, Frédéric; Klazar, Martin; Kratochvíl, Jan; Kratsch, Dieter; Liedloff, Mathieu
15
2011
Perfect codes in general graphs. Zbl 0858.94024
Kratochvíl, Jan
15
1991
Extending partial representations of proper and unit interval graphs. Zbl 1360.05167
Klavík, Pavel; Kratochvíl, Jan; Otachi, Yota; Rutter, Ignaz; Saitoh, Toshiki; Saumell, Maria; Vyskočil, Tomáš
15
2017
Testing planarity of partially embedded graphs. Zbl 1288.05049
Angelini, Patrizio; Di Battista, Giuseppe; Frati, Fabrizio; Jelínek, Vít; Kratochvíl, Jan; Patrignani, Maurizio; Rutter, Ignaz
15
2010
Efficient algorithms for graphs with few \(P_4\)’s. Zbl 0980.05045
Babel, Luitpold; Kloks, Ton; Kratochvil, Jan; Kratsch, Dieter; Müller, Haiko; Olariu, Stephan
14
2001
Untangling a planar graph. Zbl 1188.05092
Goaoc, Xavier; Kratochvíl, Jan; Okamoto, Yoshio; Shin, Chan-Su; Spillner, Andreas; Wolff, Alexander
14
2009
Complexity of partial covers of graphs. Zbl 1077.68725
Fiala, Jirí; Kratochvíl, Jan
14
2001
Regular codes in regular graphs are difficult. Zbl 0821.68096
Kratochvíl, Jan
14
1994
Extending partial representations of subclasses of chordal graphs. Zbl 1311.05133
Klavík, Pavel; Kratochvíl, Jan; Otachi, Yota; Saitoh, Toshiki
14
2015
Computational complexity of the distance constrained labeling problem for trees (extended abstract). Zbl 1153.68390
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
14
2008
The planar slope number of planar partial 3-trees of bounded degree. Zbl 1268.05052
Jelínek, Vít; Jelínková, Eva; Kratochvíl, Jan; Lidický, Bernard; Tesař, Marek; Vyskočil, Tomáš
14
2013
Bend-bounded path intersection graphs: sausages, noodles, and waffles on a grill. Zbl 1341.05203
Chaplick, Steven; Jelínek, Vít; Kratochvíl, Jan; Vyskočil, Tomáš
14
2012
Extending partial representations of function graphs and permutation graphs. Zbl 1365.05207
Klavík, Pavel; Kratochvíl, Jan; Krawczyk, Tomasz; Walczak, Bartosz
13
2012
Clustered planarity: small clusters in cycles and Eulerian graphs. Zbl 1194.05148
Jelínková, Eva; Kára, Jan; Kratochvíl, Jan; Pergel, Martin; Suchý, Ondřej; Vyskočil, Tomáš
13
2009
Clustered planarity: embedded clustered graphs with two-component clusters (extended abstract). Zbl 1213.68459
Jelínek, Vít; Jelínková, Eva; Kratochvíl, Jan; Lidický, Bernard
13
2009
String graphs. Zbl 0607.05031
Kratochvíl, Jan; Goljan, Miroslav; Kučera, Petr
13
1986
Extending partial representations of interval graphs. Zbl 1371.05190
Klavík, Pavel; Kratochvíl, Jan; Otachi, Yota; Saitoh, Toshiki; Vyskočil, Tomáš
13
2017
Max-tolerance graphs as intersection graphs: cliques, cycles and recognition. Zbl 1192.05102
Kaufmann, Michael; Kratochvíl, Jan; Lehmann, Katharina A.; Subramanian, Amarendran R.
13
2006
Distance constrained labeling of precolored trees. Zbl 1042.68545
Fiala, Jiří; Kratochvíl, Jan; Proskurowski, Andrzej
12
2001
Thresholds for classes of intersection graphs. Zbl 0769.05084
Janson, Svante; Kratochvíl, Jan
12
1992
Locally injective graph homomorphism: Lists guarantee dichotomy. Zbl 1167.68406
Fiala, Jiří; Kratochvíl, Jan
12
2006
Generalized domination in chordal graphs. Zbl 0849.68037
Kratochvíl, Jan; Manuel, Paul D.; Miller, Mirka
11
1995
Complexity of colored graph covers. I: Colored directed multigraphs. Zbl 0890.68095
Kratochvíl, Jan; Proskurowski, Andrzej; Telle, Jan Arne
11
1997
NP-hardness results for intersection graphs. Zbl 0697.05052
Kratochvíl, Jan; Matoušek, Jiří
11
1989
Algorithms and characterizations for 2-layer fan-planarity: from caterpillar to stegosaurus. Zbl 1358.05194
Binucci, Carla; Chimani, Markus; Didimo, Walter; Gronemann, Martin; Klein, Karsten; Kratochvíl, Jan; Montecchiani, Fabrizio; Tollis, Ioannis G.
11
2017
On the complexity of the balanced vertex ordering problem. Zbl 1153.05037
Kára, Jan; Kratochvíl, Jan; Wood, David R.
10
2007
On the computational complexity of Seidel’s switching. Zbl 0768.68047
Kratochvíl, Jan; Nešetřil, Jaroslav; Zýka, Ondřej
10
1992
Coloring precolored perfect graphs. Zbl 0876.05035
Kratochvil, Jan; Sebő, András
10
1997
On the computational complexity of partial covers of theta graphs. Zbl 1138.05061
Fiala, Jiří; Kratochvíl, Jan; Pór, Attila
9
2008
On the computational complexity of \(({\mathcal O},{\mathcal P})\)-partition problems. Zbl 0904.05074
Kratochvíl, Jan; Schiermeyer, Ingo
9
1997
Complexity of hypergraph coloring and Seidel’s switching. Zbl 1255.68082
Kratochvíl, Jan
9
2003
Planar graph coloring avoiding monochromatic subgraphs: Trees and paths make it difficult. Zbl 1095.68075
Broersma, Hajo; Fomin, Fedor V.; Kratochvil, Jan; Woeginger, Gerhard J.
9
2006
Extending partial representations of proper and unit interval graphs. Zbl 1359.05124
Klavík, Pavel; Kratochvíl, Jan; Otachi, Yota; Rutter, Ignaz; Saitoh, Toshiki; Saumell, Maria; Vyskočil, Tomáš
9
2014
Exact algorithms for \(L(2,1)\)-labeling of graphs. Zbl 1147.05310
Kratochvíl, Jan; Kratsch, Dieter; Liedloff, Mathieu
9
2007
Parameterized complexity of generalized domination problems. Zbl 1241.05108
Golovach, Petr A.; Kratochvíl, Jan; Suchý, Ondřej
8
2012
Algorithmic aspects of regular graph covers with applications to planar graphs. Zbl 1416.05224
Fiala, Jiří; Klavík, Pavel; Kratochvíl, Jan; Nedela, Roman
8
2014
Firefighting on square, hexagonal, and triangular grids. Zbl 1301.05241
Gavenčiak, Tomáš; Kratochvíl, Jan; Prałat, Paweł
8
2014
Simultaneous orthogonal planarity. Zbl 1478.68211
Angelini, Patrizio; Chaplick, Steven; Cornelsen, Sabine; Da Lozzo, Giordano; Di Battista, Giuseppe; Eades, Peter; Kindermann, Philipp; Kratochvíl, Jan; Lipp, Fabian; Rutter, Ignaz
8
2016
Extending partial representations of interval graphs. Zbl 1331.68107
Klavík, Pavel; Kratochvíl, Jan; Vyskočil, Tomáš
7
2011
Parameterized complexity of coloring problems: treewidth versus vertex cover (extended abstract). Zbl 1241.68071
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
7
2009
On intersection representations of co-planar graphs. Zbl 0897.05030
Kratochvíl, Jan; Kuběna, Aleš
7
1998
Mixed hypercacti. Zbl 1064.05060
Král’, Daniel; Kratochvíl, Jan; Voss, Heinz-Jürgen
7
2004
Drawing simultaneously embedded graphs with few bends. Zbl 1426.68212
Grilli, Luca; Hong, Seok-Hee; Kratochvíl, Jan; Rutter, Ignaz
7
2014
Computational complexity of generalized domination: A complete dichotomy for chordal graphs. Zbl 1141.68530
Golovach, Petr; Kratochvíl, Jan
6
2007
Distance three labelings of trees. Zbl 1241.05123
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan; Lidický, Bernard; Paulusma, Daniël
6
2012
Coloring mixed hypertrees. Zbl 0989.05111
Král, Daniel; Kratochvíl, Jan; Proskurowski, Andrzej; Voss, Heinz-Jürgen
6
2000
Computing the branchwidth of interval graphs. Zbl 1084.05068
Kloks, Ton; Kratochvíl, Jan; Müller, Haiko
6
2005
Intersection dimensions of graph classes. Zbl 0808.05092
Kratochvíl, Jan; Tuza, Zsolt
6
1994
Mixed hypergraphs with bounded degree: Edge-coloring of mixed multigraphs. Zbl 1051.68114
Král’, Daniel; Kratochvíl, Jan; Voss, Heinz-Jürgen
6
2003
Clustered planarity: Small clusters in Eulerian graphs. Zbl 1137.68495
Jelínková, Eva; Kára, Jan; Kratochvíl, Jan; Pergel, Martin; Suchý, Ondřej; Vyskočil, Tomáš
5
2008
Fixed parameter tractability of independent set in segment intersection graphs. Zbl 1154.68428
Kára, Jan; Kratochvíl, Jan
5
2006
Coloring mixed hypertrees. Zbl 1088.05031
Král, Daniel; Kratochvíl, Jan; Proskurowski, Andrzej; Voss, Heinz-Jürgen
5
2006
Cops, a fast robber and defensive domination on interval graphs. Zbl 1433.91033
Dereniowski, Dariusz; Gavenčiak, Tomáš; Kratochvíl, Jan
5
2019
On switching to \(H\)-free graphs. Zbl 1292.05247
Jelínková, Eva; Kratochvíl, Jan
5
2014
3-connected reduction for regular graph covers. Zbl 1393.05207
Fiala, Jiří; Klavík, Pavel; Kratochvíl, Jan; Nedela, Roman
5
2018
Parameterized complexity of distance labeling and uniform channel assignment problems. Zbl 1395.05143
Fiala, Jiří; Gavenčiak, Tomáš; Knop, Dušan; Koutecký, Martin; Kratochvíl, Jan
5
2018
Cops and robbers on intersection graphs. Zbl 1390.05145
Gavenčiak, Tomáš; Gordinowicz, Przemysław; Jelínek, Vít; Klavík, Pavel; Kratochvíl, Jan
5
2018
On the computational complexity of codes in graphs. Zbl 0655.68039
Kratochvíl, Jan; Křivánek, Mirko
4
1988
Moving vertices to make drawings plane. Zbl 1137.68490
Goaoc, Xavier; Kratochvíl, Jan; Okamoto, Yoshio; Shin, Chan-Su; Wolff, Alexander
4
2008
On the computational complexity of degenerate unit distance representations of graphs. Zbl 1326.68160
Horvat, Boris; Kratochvíl, Jan; Pisanski, Tomaž
4
2011
On the complexity of reconstructing \(H\)-free graphs from their star systems. Zbl 1230.05215
Fomin, Fedor V.; Kratochvíl, Jan; Lokshtanov, Daniel; Mancini, Federico; Telle, Jan Arne
4
2011
Complexity of choosing subsets from color sets. Zbl 0956.05095
Kratochvíl, J.; Tuza, Zsolt; Voigt, Margit
4
1998
The Rique-number of graphs. Zbl 07727774
Bekos, Michael A.; Felsner, Stefan; Kindermann, Philipp; Kobourov, Stephen; Kratochvíl, Jan; Rutter, Ignaz
1
2023
List covering of regular multigraphs. Zbl 07577702
Bok, Jan; Fiala, Jiří; Jedličková, Nikola; Kratochvíl, Jan; Rzążewski, Paweł
1
2022
Computational complexity of covering disconnected multigraphs. Zbl 07530226
Bok, Jan; Fiala, Jiří; Jedličková, Nikola; Kratochvíl, Jan; Seifrtová, Michaela
3
2021
\(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited. Zbl 1518.68270
Kratochvíl, Jan; Masařík, Tomáš; Novotná, Jana
1
2021
The stub resolution of 1-planar graphs. Zbl 1489.05030
Kaufmann, Michael; Kratochvil, Jan; Lipp, Fabian; Montecchiani, Fabrizio; Raftopoulou, Chrysanthi; Valtr, Pavel
1
2021
U-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited. Zbl 1518.68271
Kratochvíl, Jan; Masařík, Tomáš; Novotná, Jana
3
2020
The stub resolution of 1-planar graphs. Zbl 07224282
Kaufmann, Michael; Kratochvil, Jan; Lipp, Fabian; Montecchiani, Fabrizio; Raftopoulou, Chrysanthi; Valtr, Pavel
1
2020
Cops, a fast robber and defensive domination on interval graphs. Zbl 1433.91033
Dereniowski, Dariusz; Gavenčiak, Tomáš; Kratochvíl, Jan
5
2019
3-connected reduction for regular graph covers. Zbl 1393.05207
Fiala, Jiří; Klavík, Pavel; Kratochvíl, Jan; Nedela, Roman
5
2018
Parameterized complexity of distance labeling and uniform channel assignment problems. Zbl 1395.05143
Fiala, Jiří; Gavenčiak, Tomáš; Knop, Dušan; Koutecký, Martin; Kratochvíl, Jan
5
2018
Cops and robbers on intersection graphs. Zbl 1390.05145
Gavenčiak, Tomáš; Gordinowicz, Przemysław; Jelínek, Vít; Klavík, Pavel; Kratochvíl, Jan
5
2018
Completion of the mixed unit interval graphs hierarchy. Zbl 1386.05163
Talon, Alexandre; Kratochvíl, Jan
2
2018
On vertex- and empty-ply proximity drawings. Zbl 1503.68202
Angelini, Patrizio; Chaplick, Steven; De Luca, Felice; Fiala, Jiří; Hančl, Jaroslav jun.; Heinsohn, Niklas; Kaufmann, Michael; Kobourov, Stephen; Kratochvíl, Jan; Valtr, Pavel
2
2018
Bounded stub resolution for some maximal 1-planar graphs. Zbl 1497.68384
Kaufmann, Michael; Kratochvíl, Jan; Lipp, Fabian; Montecchiani, Fabrizio; Raftopoulou, Chrysanthi; Valtr, Pavel
1
2018
Homothetic polygons and beyond: maximal cliques in intersection graphs. Zbl 1394.05106
Brimkov, Valentin E.; Junosza-Szaniawski, Konstanty; Kafer, Sean; Kratochvíl, Jan; Pergel, Martin; Rzążewski, Paweł; Szczepankiewicz, Matthew; Terhaar, Joshua
1
2018
Extending partial representations of proper and unit interval graphs. Zbl 1360.05167
Klavík, Pavel; Kratochvíl, Jan; Otachi, Yota; Rutter, Ignaz; Saitoh, Toshiki; Saumell, Maria; Vyskočil, Tomáš
15
2017
Extending partial representations of interval graphs. Zbl 1371.05190
Klavík, Pavel; Kratochvíl, Jan; Otachi, Yota; Saitoh, Toshiki; Vyskočil, Tomáš
13
2017
Algorithms and characterizations for 2-layer fan-planarity: from caterpillar to stegosaurus. Zbl 1358.05194
Binucci, Carla; Chimani, Markus; Didimo, Walter; Gronemann, Martin; Klein, Karsten; Kratochvíl, Jan; Montecchiani, Fabrizio; Tollis, Ioannis G.
11
2017
Simultaneous orthogonal planarity. Zbl 1478.68211
Angelini, Patrizio; Chaplick, Steven; Cornelsen, Sabine; Da Lozzo, Giordano; Di Battista, Giuseppe; Eades, Peter; Kindermann, Philipp; Kratochvíl, Jan; Lipp, Fabian; Rutter, Ignaz
8
2016
Computational complexity of covering three-vertex multigraphs. Zbl 1331.68108
Kratochvíl, Jan; Telle, Jan Arne; Tesař, Marek
2
2016
Fixed parameter complexity of distance constrained labeling and uniform channel assignment problems (extended abstract). Zbl 1476.68207
Fiala, Jiří; Gavenčiak, Tomáš; Knop, Dušan; Koutecký, Martin; Kratochvíl, Jan
1
2016
On the hardness of switching to a small number of edges. Zbl 1477.68232
Jelínek, Vít; Jelínková, Eva; Kratochvíl, Jan
1
2016
Testing planarity of partially embedded graphs. Zbl 1398.68385
Angelini, Patrizio; Di Battista, Giuseppe; Frati, Fabrizio; Jelínek, Vít; Kratochvíl, Jan; Patrignani, Maurizio; Rutter, Ignaz
28
2015
Extending partial representations of subclasses of chordal graphs. Zbl 1311.05133
Klavík, Pavel; Kratochvíl, Jan; Otachi, Yota; Saitoh, Toshiki
14
2015
Cops and Robbers on string graphs. Zbl 1447.05134
Gavenčiak, Tomáš; Gordinowicz, Przemysław; Jelínek, Vít; Klavík, Pavel; Kratochvíl, Jan
1
2015
Contact representations of planar graphs: extending a partial representation is hard. Zbl 1417.05133
Chaplick, Steven; Dorbec, Paul; Kratochvíl, Jan; Montassier, Mickael; Stacho, Juraj
19
2014
Extending partial representations of proper and unit interval graphs. Zbl 1359.05124
Klavík, Pavel; Kratochvíl, Jan; Otachi, Yota; Rutter, Ignaz; Saitoh, Toshiki; Saumell, Maria; Vyskočil, Tomáš
9
2014
Algorithmic aspects of regular graph covers with applications to planar graphs. Zbl 1416.05224
Fiala, Jiří; Klavík, Pavel; Kratochvíl, Jan; Nedela, Roman
8
2014
Firefighting on square, hexagonal, and triangular grids. Zbl 1301.05241
Gavenčiak, Tomáš; Kratochvíl, Jan; Prałat, Paweł
8
2014
Drawing simultaneously embedded graphs with few bends. Zbl 1426.68212
Grilli, Luca; Hong, Seok-Hee; Kratochvíl, Jan; Rutter, Ignaz
7
2014
On switching to \(H\)-free graphs. Zbl 1292.05247
Jelínková, Eva; Kratochvíl, Jan
5
2014
Planar embeddings with small and uniform faces. Zbl 1432.68347
Da Lozzo, Giordano; Jelínek, Vít; Kratochvíl, Jan; Rutter, Ignaz
4
2014
Locally injective \(k\)-colourings of planar graphs. Zbl 1298.05124
Kratochvil, Jan; Siggers, Mark
1
2014
A Kuratowski-type theorem for planarity of partially embedded graphs. Zbl 1259.05044
Jelínek, Vít; Kratochvíl, Jan; Rutter, Ignaz
18
2013
The planar slope number of planar partial 3-trees of bounded degree. Zbl 1268.05052
Jelínek, Vít; Jelínková, Eva; Kratochvíl, Jan; Lidický, Bernard; Tesař, Marek; Vyskočil, Tomáš
14
2013
Non-crossing connectors in the plane. Zbl 1382.68264
Kratochvíl, Jan; Ueckerdt, Torsten
3
2013
Cops and robbers on intersection graphs. Zbl 1329.05209
Gavenčiak, Tomás; Jelínek, Vít; Klavík, Pavel; Kratochvíl, Jan
3
2013
Fast exact algorithm for \(L(2,1)\)-labeling of graphs. Zbl 1417.05214
Junosza-Szaniawski, Konstanty; Kratochvíl, Jan; Liedloff, Mathieu; Rossmanith, Peter; Rzążewski, Paweł
3
2013
Cluster vertex deletion: a parameterization between vertex cover and clique-width. Zbl 1365.68278
Doucha, Martin; Kratochvíl, Jan
23
2012
Bend-bounded path intersection graphs: sausages, noodles, and waffles on a grill. Zbl 1341.05203
Chaplick, Steven; Jelínek, Vít; Kratochvíl, Jan; Vyskočil, Tomáš
14
2012
Extending partial representations of function graphs and permutation graphs. Zbl 1365.05207
Klavík, Pavel; Kratochvíl, Jan; Krawczyk, Tomasz; Walczak, Bartosz
13
2012
Parameterized complexity of generalized domination problems. Zbl 1241.05108
Golovach, Petr A.; Kratochvíl, Jan; Suchý, Ondřej
8
2012
Distance three labelings of trees. Zbl 1241.05123
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan; Lidický, Bernard; Paulusma, Daniël
6
2012
Segment representation of a subclass of co-planar graphs. Zbl 1242.05067
Francis, Mathew C.; Kratochvíl, Jan; Vyskočil, Tomáš
3
2012
Extending partial representations of subclasses of chordal graphs. Zbl 1260.68180
Klavík, Pavel; Kratochvíl, Jan; Otachi, Yota; Saitoh, Toshiki
3
2012
Determining the \(L(2,1)\)-span in polynomial space. Zbl 1341.05223
Junosza-Szaniawski, Konstanty; Kratochvíl, Jan; Liedloff, Mathieu; Rzążewski, Paweł
1
2012
MSOL restricted contractibility to planar graphs. Zbl 1374.68236
Abello, James; Klavík, Pavel; Kratochvíl, Jan; Vyskočil, Tomáš
1
2012
Beyond homothetic polygons: recognition and maximum clique. Zbl 1260.68417
Junosza-Szaniawski, Konstanty; Kratochvíl, Jan; Pergel, Martin; Rzążewski, Paweł
1
2012
Parameterized complexity of coloring problems: treewidth versus vertex cover. Zbl 1216.68127
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
36
2011
Exact algorithms for \(L(2,1)\)-labeling of graphs. Zbl 1213.68455
Havet, Frédéric; Klazar, Martin; Kratochvíl, Jan; Kratsch, Dieter; Liedloff, Mathieu
15
2011
Extending partial representations of interval graphs. Zbl 1331.68107
Klavík, Pavel; Kratochvíl, Jan; Vyskočil, Tomáš
7
2011
On the computational complexity of degenerate unit distance representations of graphs. Zbl 1326.68160
Horvat, Boris; Kratochvíl, Jan; Pisanski, Tomaž
4
2011
On the complexity of reconstructing \(H\)-free graphs from their star systems. Zbl 1230.05215
Fomin, Fedor V.; Kratochvíl, Jan; Lokshtanov, Daniel; Mancini, Federico; Telle, Jan Arne
4
2011
Parameterized problems related to Seidel’s switching. Zbl 1283.68164
Jelinkova, Eva; Suchy, Ondrej; Hlineny, Petr; Kratochvil, Jan
4
2011
Fast exact algorithm for \(L(2,1)\)-labeling of graphs. Zbl 1333.05292
Junosza-Szaniawski, Konstanty; Kratochvíl, Jan; Liedloff, Mathieu; Rossmanith, Peter; Rzążewski, Paweł
2
2011
Can they cross? and how? (the hitchhiker’s guide to the universe of geometric intersection graphs). Zbl 1283.68371
Kratochvil, Jan
2
2011
Pursuing a fast robber on a graph. Zbl 1192.91027
Fomin, Fedor V.; Golovach, Petr A.; Kratochvíl, Jan; Nisse, Nicolas; Suchan, Karol
36
2010
Testing planarity of partially embedded graphs. Zbl 1288.05049
Angelini, Patrizio; Di Battista, Giuseppe; Frati, Fabrizio; Jelínek, Vít; Kratochvíl, Jan; Patrignani, Maurizio; Rutter, Ignaz
15
2010
The planar slope number of planar partial 3-trees of bounded degree. Zbl 1284.68465
Jelínek, Vít; Jelínková, Eva; Kratochvíl, Jan; Lidický, Bernard; Tesař, Marek; Vyskočil, Tomáš
4
2010
Parameterized complexity of generalized domination problems. Zbl 1273.68171
Golovach, Petr A.; Kratochvíl, Jan; Suchý, Ondřej
2
2010
Faithful representations of graphs by islands in the extended grid. Zbl 1283.68269
Coury, Michael D.; Hell, Pavol; Kratochvíl, Jan; Vyskočil, Tomáš
1
2010
On the computation of the hull number of a graph. Zbl 1215.05184
Dourado, Mitre C.; Gimbel, John G.; Kratochvíl, Jan; Protti, Fábio; Szwarcfiter, Jayme L.
53
2009
The capture time of a graph. Zbl 1177.91056
Bonato, A.; Golovach, P.; Hahn, G.; Kratochvíl, J.
34
2009
Untangling a planar graph. Zbl 1188.05092
Goaoc, Xavier; Kratochvíl, Jan; Okamoto, Yoshio; Shin, Chan-Su; Spillner, Andreas; Wolff, Alexander
14
2009
Clustered planarity: small clusters in cycles and Eulerian graphs. Zbl 1194.05148
Jelínková, Eva; Kára, Jan; Kratochvíl, Jan; Pergel, Martin; Suchý, Ondřej; Vyskočil, Tomáš
13
2009
Clustered planarity: embedded clustered graphs with two-component clusters (extended abstract). Zbl 1213.68459
Jelínek, Vít; Jelínková, Eva; Kratochvíl, Jan; Lidický, Bernard
13
2009
Parameterized complexity of coloring problems: treewidth versus vertex cover (extended abstract). Zbl 1241.68071
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
7
2009
Sort and Search: exact algorithms for generalized domination. Zbl 1197.05104
Fomin, Fedor V.; Golovach, Petr A.; Kratochvíl, Jan; Kratsch, Dieter; Liedloff, Mathieu
3
2009
Locally constrained graph homomorphisms – structure, complexity, and applications. Zbl 1302.05122
Fiala, Jiří; Kratochvíl, Jan
28
2008
Computational complexity of the distance constrained labeling problem for trees (extended abstract). Zbl 1153.68390
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
14
2008
On the computational complexity of partial covers of theta graphs. Zbl 1138.05061
Fiala, Jiří; Kratochvíl, Jan; Pór, Attila
9
2008
Clustered planarity: Small clusters in Eulerian graphs. Zbl 1137.68495
Jelínková, Eva; Kára, Jan; Kratochvíl, Jan; Pergel, Martin; Suchý, Ondřej; Vyskočil, Tomáš
5
2008
Moving vertices to make drawings plane. Zbl 1137.68490
Goaoc, Xavier; Kratochvíl, Jan; Okamoto, Yoshio; Shin, Chan-Su; Wolff, Alexander
4
2008
Generalized domination in degenerate graphs: A complete dichotomy of computational complexity. Zbl 1139.68344
Golovach, Petr; Kratochvíl, Jan
2
2008
Intersection graphs of homothetic polygons. Zbl 1267.05177
Kratochvíl, Jan; Pergel, Martin
2
2008
On the complexity of reconstructing \(H\)-free graphs from their star systems. Zbl 1136.68459
Fomin, Fedor V.; Kratochvíl, Jan; Lokshtanov, Daniel; Mancini, Federico; Telle, Jan Arne
1
2008
Distance constrained labelings of trees. Zbl 1139.05341
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
1
2008
On switching to \(H\)-free graphs. Zbl 1175.68298
Jelínková, Eva; Kratochvíl, Jan
1
2008
On the complexity of the balanced vertex ordering problem. Zbl 1153.05037
Kára, Jan; Kratochvíl, Jan; Wood, David R.
10
2007
Exact algorithms for \(L(2,1)\)-labeling of graphs. Zbl 1147.05310
Kratochvíl, Jan; Kratsch, Dieter; Liedloff, Mathieu
9
2007
Computational complexity of generalized domination: A complete dichotomy for chordal graphs. Zbl 1141.68530
Golovach, Petr; Kratochvíl, Jan
6
2007
Geometric intersection graphs: do short cycles help? (Extended abstract). Zbl 1206.05069
Kratochvíl, Jan; Pergel, Martin
3
2007
Branch and recharge: exact algorithms for generalized domination. Zbl 1209.05240
Fomin, Fedor V.; Golovach, Petr A.; Kratochvíl, Jan; Kratsch, Dieter; Liedloff, Mathieu
1
2007
Max-tolerance graphs as intersection graphs: cliques, cycles and recognition. Zbl 1192.05102
Kaufmann, Michael; Kratochvíl, Jan; Lehmann, Katharina A.; Subramanian, Amarendran R.
13
2006
Locally injective graph homomorphism: Lists guarantee dichotomy. Zbl 1167.68406
Fiala, Jiří; Kratochvíl, Jan
12
2006
Planar graph coloring avoiding monochromatic subgraphs: Trees and paths make it difficult. Zbl 1095.68075
Broersma, Hajo; Fomin, Fedor V.; Kratochvil, Jan; Woeginger, Gerhard J.
9
2006
Fixed parameter tractability of independent set in segment intersection graphs. Zbl 1154.68428
Kára, Jan; Kratochvíl, Jan
5
2006
Coloring mixed hypertrees. Zbl 1088.05031
Král, Daniel; Kratochvíl, Jan; Proskurowski, Andrzej; Voss, Heinz-Jürgen
5
2006
Distance constrained labelings of graphs of bounded treewidth. Zbl 1082.68080
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
25
2005
Systems of distant representatives. Zbl 1084.05059
Fiala, Jiří; Kratochvíl, Jan; Proskurowski, Andrzej
22
2005
Computing the branchwidth of interval graphs. Zbl 1084.05068
Kloks, Ton; Kratochvíl, Jan; Müller, Haiko
6
2005
On the complexity of the balanced vertex ordering problem. Zbl 1128.68402
Kára, Jan; Kratochvíl, Jan; Wood, David R.
4
2005
On the computational complexity of the \(L_{(2,1)}\)-labeling problem for regular graphs. Zbl 1171.68612
Fiala, Jiří; Kratochvíl, Jan
3
2005
On the computational complexity of partial covers of theta graphs. Zbl 1203.05152
Fiala, Jiří; Kratochvíl, Jan; Pór, Attila
2
2005
Mixed hypercacti. Zbl 1064.05060
Král’, Daniel; Kratochvíl, Jan; Voss, Heinz-Jürgen
7
2004
Two results on intersection graphs of polygons. Zbl 1215.05117
Kratochvíl, Jan; Pergel, Martin
3
2004
Elegant distance constrained labelings of trees. Zbl 1112.68419
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
2
2004
Complexity of hypergraph coloring and Seidel’s switching. Zbl 1255.68082
Kratochvíl, Jan
9
2003
Mixed hypergraphs with bounded degree: Edge-coloring of mixed multigraphs. Zbl 1051.68114
Král’, Daniel; Kratochvíl, Jan; Voss, Heinz-Jürgen
6
2003
On the injective chromatic number of graphs. Zbl 1007.05046
Hahn, Geňa; Kratochvíl, Jan; Širáň, Jozef; Sotteau, Dominique
85
2002
...and 63 more Documents
all top 5

Cited by 1,767 Authors

73 Paulusma, Daniël
66 Kratochvíl, Jan
48 Golovach, Petr A.
27 Rutter, Ignaz
25 Fiala, Jiří
25 Rzążewski, Paweł
24 Angelini, Patrizio
23 Dourado, Mitre Costa
22 Chandran, L. Sunil
22 Chaplick, Steven
18 Liotta, Giuseppe
17 Da Lozzo, Giordano
17 Fomin, Fedor V.
16 Dabrowski, Konrad Kazimierz
16 Otachi, Yota
16 Ries, Bernard
15 Lozin, Vadim Vladislavovich
15 Malyshev, Dmitriĭ Sergeevich
14 Klavík, Pavel
14 Král’, Daniel
14 Martin, Barnaby D.
14 Montecchiani, Fabrizio
14 Sampaio, Rudini Menezes
13 Niedermeier, Rolf
13 Tuza, Zsolt
12 Bekos, Michael A.
12 Frati, Fabrizio
12 Kindermann, Philipp
12 Klavžar, Sandi
12 Kobourov, Stephen G.
12 Maffray, Frédéric
12 Ono, Hirotaka
12 Pach, János
12 Rautenbach, Dieter
11 Francis, Mathew C.
11 Linhares-Sales, Claudia
11 Protti, Fábio
11 Smith, Siani
11 Szwarcfiter, Jayme Luiz
11 Zhou, Sanming
10 Bonomo-Braberman, Flavia
10 Chudnovsky, Maria
10 Di Giacomo, Emilio
10 Gavril, Fanica
10 Junosza-Szaniawski, Konstanty
10 Lidický, Bernard
10 Liedloff, Mathieu
10 Mondal, Debajyoti
10 Nöllenburg, Martin
10 Prałat, Paweł
10 Raspaud, André
10 Schaefer, Marcus
10 Schaudt, Oliver
10 Song, Jian
10 Telle, Jan Arne
10 Van Leeuwen, Erik Jan
10 Wolff, Alexander
9 Bonato, Anthony
9 Bu, Yuehua
9 Campos, Victor A.
9 Cardoso, Domingos Moreira
9 Di Battista, Giuseppe
9 Esperet, Louis
9 Hell, Pavol
9 Johnson, Matthew
9 Knop, Dušan
9 Kratsch, Dieter
9 Liang, Zuosong
9 Mchedlidze, Tamara
9 Sivadasan, Naveen
9 Walczak, Bartosz
8 Belmonte, Rémy
8 Dantas, Simone
8 Felsner, Stefan
8 Gavenčiak, Tomáš
8 Hanaka, Tesshu
8 Hoàng, Chính T.
8 Kamiński, Marcin Marek
8 Kaufmann, Michael
8 Löffler, Maarten
8 Martins, Nicolas Almeida
8 Ochem, Pascal
8 Stacho, Juraj
8 Stein, Maya Jakobine
7 Chakraborty, Dibyayan
7 Das, Sandip
7 Fulek, Radoslav
7 Gonçalves, Daniel
7 Jansen, Klaus
7 Lampis, Michael
7 Lima, Paloma T.
7 Lokshtanov, Daniel
7 Milanič, Martin
7 Mohar, Bojan
7 Nichterlein, André
7 Patrignani, Maurizio
7 Peterin, Iztok
7 Shan, Erfang
7 Shao, Zhendong
7 Štefankovič, Daniel
...and 1,667 more Authors
all top 5

Cited in 135 Serials

209 Discrete Applied Mathematics
134 Theoretical Computer Science
118 Discrete Mathematics
72 Algorithmica
44 Information Processing Letters
36 Graphs and Combinatorics
31 European Journal of Combinatorics
30 Journal of Graph Algorithms and Applications
28 SIAM Journal on Discrete Mathematics
25 Journal of Combinatorial Theory. Series B
24 Journal of Combinatorial Optimization
23 Discrete & Computational Geometry
22 Journal of Graph Theory
22 Computational Geometry
18 The Electronic Journal of Combinatorics
16 Discrete Mathematics, Algorithms and Applications
15 Journal of Discrete Algorithms
14 Journal of Computer and System Sciences
14 Discussiones Mathematicae. Graph Theory
13 Theory of Computing Systems
11 Applied Mathematics and Computation
7 Information and Computation
7 Annals of Operations Research
7 Discrete Optimization
6 Networks
6 Combinatorica
6 European Journal of Operational Research
6 Combinatorics, Probability and Computing
5 Journal of Combinatorial Theory. Series A
5 Applied Mathematics Letters
5 Linear Algebra and its Applications
4 Order
4 Random Structures & Algorithms
4 Designs, Codes and Cryptography
4 Mathematical Programming. Series A. Series B
4 Journal of Mathematical Sciences (New York)
4 Bulletin of the Malaysian Mathematical Sciences Society. Second Series
4 Optimization Letters
4 Diskretnyĭ Analiz i Issledovanie Operatsiĭ
4 Computer Science Review
3 Advances in Mathematics
3 Advances in Applied Mathematics
3 International Journal of Foundations of Computer Science
3 CEJOR. Central European Journal of Operations Research
3 Trudy Instituta Matematiki
3 AKCE International Journal of Graphs and Combinatorics
3 Ars Mathematica Contemporanea
2 Acta Informatica
2 Artificial Intelligence
2 Computers & Mathematics with Applications
2 Israel Journal of Mathematics
2 Bulletin of the London Mathematical Society
2 Information Sciences
2 Bulletin of the Korean Mathematical Society
2 Computers & Operations Research
2 International Journal of Computer Mathematics
2 The Australasian Journal of Combinatorics
2 Opuscula Mathematica
2 International Transactions in Operational Research
2 Vietnam Journal of Mathematics
2 Journal of Discrete Mathematical Sciences & Cryptography
2 Mathematics in Computer Science
2 Frontiers of Mathematics in China
2 Algorithms
2 Journal of Mathematical Research with Applications
2 Proceedings of the Yerevan State University. Physical and Mathematical Sciences
2 CGT. Computing in Geometry and Topology
1 American Mathematical Monthly
1 Bulletin of the Australian Mathematical Society
1 Communications in Algebra
1 Journal of Mathematical Biology
1 Archiv der Mathematik
1 BIT
1 Czechoslovak Mathematical Journal
1 Journal of Applied Probability
1 Journal of Geometry
1 Journal of the London Mathematical Society. Second Series
1 Journal of Pure and Applied Algebra
1 Proceedings of the American Mathematical Society
1 Ricerche di Matematica
1 Siberian Mathematical Journal
1 Transactions of the American Mathematical Society
1 Operations Research Letters
1 Advances in Mathematics (Beijing)
1 Bulletin of the Iranian Mathematical Society
1 Acta Mathematicae Applicatae Sinica. English Series
1 Probability Theory and Related Fields
1 Journal of Computer Science and Technology
1 Journal of Parallel and Distributed Computing
1 International Journal of Computational Geometry & Applications
1 The Annals of Applied Probability
1 Applied Mathematical Modelling
1 Automation and Remote Control
1 Journal of Mathematical Imaging and Vision
1 Journal of Algebraic Combinatorics
1 Computational and Applied Mathematics
1 Journal of the Egyptian Mathematical Society
1 Filomat
1 Finite Fields and their Applications
1 Annals of Mathematics and Artificial Intelligence
...and 35 more Serials

Citations by Year

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.