×

zbMATH — the first resource for mathematics

Kratochvíl, Jan

Compute Distance To:
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
Documents Indexed: 201 Publications since 1983, including 17 Books
all top 5

Co-Authors

16 single-authored
29 Fiala, Jiří
16 Golovach, Petr A.
14 Klavík, Pavel
13 Jelínek, Vít
13 Vyskočil, Tomáš
12 Proskurowski, Andrzej
12 Tuza, Zsolt
11 Telle, Jan Arne
10 Nešetřil, Jaroslav
9 Jelínková, Eva
9 Liedloff, Mathieu
9 Rutter, Ignaz
8 Fomin, Fedor V.
7 Gavenčiak, Tomáš
7 Miller, Mirka
7 Pergel, Martin
6 Junosza-Szaniawski, Konstanty
6 Král’, Daniel
6 Kratsch, Dieter
6 Rzążewski, Paweł
5 Kára, Jan
5 Kloks, Ton
5 Matoušek, Jiří
5 Otachi, Yota
5 Saitoh, Toshiki
5 Suchý, Ondřej
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 Montecchiani, Fabrizio
4 Tesař, Marek
4 Valtr, Pavel
4 Voigt, Margit
3 Di Battista, Giuseppe
3 Fiedler, Miroslav
3 Heggernes, Pinar
3 Kaufmann, Michael
3 Lipp, Fabian
3 Manuel, Paul D.
3 Müller, Haiko
3 Nedela, Roman
3 Woeginger, Gerhard Johannes
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 Gronemann, Martin
2 Hahn, Gena
2 Hell, Pavol
2 Janson, Svante
2 Klazar, Martin
2 Klein, Karsten
2 Knop, Dušan
2 Kolman, Petr
2 Koubek, Vaclav
2 Koutecký, Martin
2 Křivánek, Mirko
2 Li, Angsheng
2 Lokshtanov, Daniel
2 Mancini, Federico
2 Middendorf, Matthias
2 Mihók, Peter
2 Okamoto, Yoshio
2 Patrignani, Maurizio
2 Pfeiffer, Frank
2 Pór, Attila
2 Raftopoulou, Chrysanthi N.
2 Rosenfeld, Moshe
2 Rossmanith, Peter
2 Saumell, Maria
2 Shin, Chan-Su
2 Talon, Alexandre
2 Tollis, Ioannis G.
2 Wolff, Alexander
2 Wood, David Ronald
2 Zeps, Dainis A.
1 Babel, Luitpold
1 Bonato, Anthony
1 Brimkov, Valentin E.
1 Cornelsen, Sabine
1 Coury, Michael D.
1 Dahlhaus, Elias
1 de Fraysseix, Hubert
1 De Luca, Felice
1 Dereniowski, Dariusz
1 Díaz, Josep
1 Dorbec, Paul
1 Doucha, Martin
1 Dourado, Mitre C.
1 Eades, Peter
1 Francis, Mathew C.
...and 59 more Co-Authors

Publications by Year

Citations contained in zbMATH Open

143 Publications have been cited 1,480 times in 1,049 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.
75
2001
A special planar satisfiability problem and a consequence of its NP- completeness. Zbl 0810.68083
Kratochvíl, Jan
69
1994
On the \(b\)-chromatic number of graphs. Zbl 1024.05026
Kratochvíl, Jan; Tuza, Zsolt; Voigt, Margit
58
2002
On the injective chromatic number of graphs. Zbl 1007.05046
Hahn, Geňa; Kratochvíl, Jan; Širáň, Jozef; Sotteau, Dominique
56
2002
Fixed-parameter complexity of \(\lambda\)-labelings. Zbl 0982.05085
Fiala, Jiří; Kloks, Ton; Kratochvíl, Jan
50
2001
String graphs. II: Recognizing string graphs is NP-hard. Zbl 0661.05054
Kratochvíl, Jan
39
1991
Intersection graphs of segments. Zbl 0808.68075
Kratochvíl, Jan; Matoušek, Jiří
39
1994
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.
38
2009
Covering and coloring polygon-circle graphs. Zbl 0871.05025
Kostochka, Alexandr; Kratochvíl, Jan
33
1997
Perfect codes over graphs. Zbl 0563.94017
Kratochvíl, Jan
31
1986
String graphs requiring exponential representations. Zbl 0675.05059
Kratochvíl, Jan; Matoušek, Jiří
28
1991
Pursuing a fast robber on a graph. Zbl 1192.91027
Fomin, Fedor V.; Golovach, Petr A.; Kratochvíl, Jan; Nisse, Nicolas; Suchan, Karol
28
2010
On the complexity of bicoloring clique hypergraphs of graphs. Zbl 1030.68066
Kratochvíl, Jan; Tuza, Zsolt
27
2002
Precoloring extension with fixed color bound. Zbl 0821.05027
Kratochvíl, J.
25
1993
The complexity of induced minors and related problems. Zbl 0816.68070
Fellows, M. R.; Kratochvíl, J.; Middendorf, M.; Pfeiffer, F.
24
1995
The capture time of a graph. Zbl 1177.91056
Bonato, A.; Golovach, P.; Hahn, G.; Kratochvíl, J.
24
2009
INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs. Zbl 0727.05056
Kratochvíl, Jan; Nešetřil, Jaroslav
22
1990
Partial covers of graphs. Zbl 1017.05094
Fiala, Jiří; Kratochvíl, Jan
21
2002
Locally constrained graph homomorphisms – structure, complexity, and applications. Zbl 1302.05122
Fiala, Jiří; Kratochvíl, Jan
20
2008
Algorithmic complexity of list colorings. Zbl 0807.68055
Kratochvíl, Jan; Tuza, Zsolt
20
1994
Covering regular graphs. Zbl 0895.05049
Kratochvíl, Jan; Proskurowski, Andrzej; Telle, Jan Arne
20
1997
Parameterized complexity of coloring problems: treewidth versus vertex cover. Zbl 1216.68127
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
19
2011
One more occurrence of variables makes satisfiability jump from trivial to NP-complete. Zbl 0767.68057
Kratochvíl, Jan; Savický, Petr; Tuza, Zsolt
18
1993
Complexity of graph covering problems. Zbl 0911.68076
Kratochvíl, Jan; Proskurowski, Andrzej; Telle, Jan Arne
17
1998
Distance constrained labelings of graphs of bounded treewidth. Zbl 1082.68080
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
17
2005
Noncrossing subgraphs in topological layouts. Zbl 0731.68047
Kratochvíl, Jan; Lubiw, Anna; Nešetřil, Jaroslav
16
1991
New trends in the theory of graph colorings: Choosability and list coloring. Zbl 1025.05030
Kratochvíl, Jan; Tuza, Zsolt; Voigt, Margit
16
1999
String graphs. I: The number of critical nonstring graphs is infinite. Zbl 0675.05058
Kratochvil, Jan
15
1991
Perfect codes in general graphs. Zbl 0858.94024
Kratochvíl, Jan
15
1991
Fixed-parameter complexity of \(\lambda\)-labelings. Zbl 0943.05072
Fiala, Jiří; Kloks, Ton; Kratochvíl, Jan
15
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
Independent sets with domination constraints. Zbl 0939.05063
Halldórsson, Magnús M.; Kratochvíl, Jan; Telle, Jan Arne
14
2000
Representing graphs by disks and balls (a survey of recognition-complexity results). Zbl 0969.68118
Hliněný, Petr; Kratochvíl, Jan
14
2001
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
Systems of distant representatives. Zbl 1084.05059
Fiala, Jiří; Kratochvíl, Jan; Proskurowski, Andrzej
14
2005
Cluster vertex deletion: a parameterization between vertex cover and clique-width. Zbl 1365.68278
Doucha, Martin; Kratochvíl, Jan
14
2012
On restricted two-factors. Zbl 0672.05065
Hell, Pavol; Kirkpatrick, David; Kratochvíl, Jan; Kříž, Igor
13
1988
Brooks-type theorems for choosability with separation. Zbl 0894.05016
Kratochvíl, J.; Tuza, Zsolt; Voigt, Margit
13
1998
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
12
2010
Regular codes in regular graphs are difficult. Zbl 0821.68096
Kratochvíl, Jan
12
1994
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áš
12
2009
Thresholds for classes of intersection graphs. Zbl 0769.05084
Janson, Svante; Kratochvíl, Jan
11
1992
Complexity of partial covers of graphs. Zbl 1077.68725
Fiala, Jirí; Kratochvíl, Jan
11
2001
Max-tolerance graphs as intersection graphs: cliques, cycles and recognition. Zbl 1192.05102
Kaufmann, Michael; Kratochvíl, Jan; Lehmann, Katharina A.; Subramanian, Amarendran R.
11
2006
Computational complexity of the distance constrained labeling problem for trees (extended abstract). Zbl 1153.68390
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
11
2008
Coloring precolored perfect graphs. Zbl 0876.05035
Kratochvil, Jan; Sebő, András
10
1997
Distance constrained labeling of precolored trees. Zbl 1042.68545
Fiala, Jiří; Kratochvíl, Jan; Proskurowski, Andrzej
10
2001
String graphs. Zbl 0607.05031
Kratochvíl, Jan; Goljan, Miroslav; Kučera, Petr
10
1986
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
10
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
10
2014
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
10
2009
A Kuratowski-type theorem for planarity of partially embedded graphs. Zbl 1259.05044
Jelínek, Vít; Kratochvíl, Jan; Rutter, Ignaz
9
2013
NP-hardness results for intersection graphs. Zbl 0697.05052
Kratochvíl, Jan; Matoušek, Jiří
9
1989
Locally injective graph homomorphism: Lists guarantee dichotomy. Zbl 1167.68406
Fiala, Jiří; Kratochvíl, Jan
9
2006
Untangling a planar graph. Zbl 1188.05092
Goaoc, Xavier; Kratochvíl, Jan; Okamoto, Yoshio; Shin, Chan-Su; Spillner, Andreas; Wolff, Alexander
9
2009
On the computational complexity of Seidel’s switching. Zbl 0768.68047
Kratochvíl, Jan; Nešetřil, Jaroslav; Zýka, Ondřej
8
1992
Generalized domination in chordal graphs. Zbl 0849.68037
Kratochvíl, Jan; Manuel, Paul D.; Miller, Mirka
8
1995
Complexity of colored graph covers. I: Colored directed multigraphs. Zbl 0890.68095
Kratochvíl, Jan; Proskurowski, Andrzej; Telle, Jan Arne
8
1997
On the computational complexity of partial covers of theta graphs. Zbl 1138.05061
Fiala, Jiří; Kratochvíl, Jan; Pór, Attila
8
2008
On the complexity of the balanced vertex ordering problem. Zbl 1153.05037
Kára, Jan; Kratochvíl, Jan; Wood, David R.
8
2007
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.
8
2006
Exact algorithms for \(L(2,1)\)-labeling of graphs. Zbl 1147.05310
Kratochvíl, Jan; Kratsch, Dieter; Liedloff, Mathieu
8
2007
On the computational complexity of \(({\mathcal O},{\mathcal P})\)-partition problems. Zbl 0904.05074
Kratochvíl, Jan; Schiermeyer, Ingo
7
1997
Mixed hypercacti. Zbl 1064.05060
Král’, Daniel; Kratochvíl, Jan; Voss, Heinz-Jürgen
7
2004
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áš
7
2013
Parameterized complexity of generalized domination problems. Zbl 1241.05108
Golovach, Petr A.; Kratochvíl, Jan; Suchý, Ondřej
7
2012
Complexity of hypergraph coloring and Seidel’s switching. Zbl 1255.68082
Kratochvíl, Jan
7
2003
Firefighting on square, hexagonal, and triangular grids. Zbl 1301.05241
Gavenčiak, Tomáš; Kratochvíl, Jan; Prałat, Paweł
6
2014
Drawing simultaneously embedded graphs with few bends. Zbl 1426.68212
Grilli, Luca; Hong, Seok-Hee; Kratochvíl, Jan; Rutter, Ignaz
6
2014
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áš
6
2017
On intersection representations of co-planar graphs. Zbl 0897.05030
Kratochvíl, Jan; Kuběna, Aleš
6
1998
Coloring mixed hypertrees. Zbl 0989.05111
Král, Daniel; Kratochvíl, Jan; Proskurowski, Andrzej; Voss, Heinz-Jürgen
6
2000
Extending partial representations of function graphs and permutation graphs. Zbl 1365.05207
Klavík, Pavel; Kratochvíl, Jan; Krawczyk, Tomasz; Walczak, Bartosz
6
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áš
6
2012
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
Parameterized complexity of coloring problems: treewidth versus vertex cover (extended abstract). Zbl 1241.68071
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
6
2009
Extending partial representations of subclasses of chordal graphs. Zbl 1311.05133
Klavík, Pavel; Kratochvíl, Jan; Otachi, Yota; Saitoh, Toshiki
5
2015
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áš
5
2014
Intersection dimensions of graph classes. Zbl 0808.05092
Kratochvíl, Jan; Tuza, Zsolt
5
1994
Computational complexity of generalized domination: A complete dichotomy for chordal graphs. Zbl 1141.68530
Golovach, Petr; Kratochvíl, Jan
5
2007
Algorithmic aspects of regular graph covers with applications to planar graphs. Zbl 1416.05224
Fiala, Jiří; Klavík, Pavel; Kratochvíl, Jan; Nedela, Roman
4
2014
Extending partial representations of interval graphs. Zbl 1371.05190
Klavík, Pavel; Kratochvíl, Jan; Otachi, Yota; Saitoh, Toshiki; Vyskočil, Tomáš
4
2017
Mod-2 independence and domination in graphs. Zbl 1320.05121
Halldórsson, Magnús M.; Kratochvíl, Jan; Telle, Jan Arne
4
2000
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.
4
2017
Coloring mixed hypertrees. Zbl 1088.05031
Král, Daniel; Kratochvíl, Jan; Proskurowski, Andrzej; Voss, Heinz-Jürgen
4
2006
New branchwidth territories. Zbl 0924.05063
Kloks, Ton; Kratochvíl, Jan; Müller, Haiko
4
1999
Computing the branchwidth of interval graphs. Zbl 1084.05068
Kloks, Ton; Kratochvíl, Jan; Müller, Haiko
4
2005
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
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
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áš
3
2010
Simultaneous orthogonal planarity. Zbl 06687322
Angelini, Patrizio; Chaplick, Steven; Cornelsen, Sabine; Da Lozzo, Giordano; Di Battista, Giuseppe; Eades, Peter; Kindermann, Philipp; Kratochvíl, Jan; Lipp, Fabian; Rutter, Ignaz
3
2016
Proportional graphs. Zbl 0765.05092
Janson, Svante; Kratochvil, Jan
3
1991
Satisfiability of co-nested formulas. Zbl 0790.68050
Kratochvíl, Jan; Křivánek, Mirko
3
1993
Mod-2 independence and domination in graphs. Zbl 0943.05081
Halldórsson, Magnús M.; Kratochvíl, Jan; Telle, Jan Arne
3
1999
Complexity of choosing subsets from color sets. Zbl 0956.05095
Kratochvíl, J.; Tuza, Zsolt; Voigt, Margit
3
1998
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
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
Fixed parameter tractability of independent set in segment intersection graphs. Zbl 1154.68428
Kára, Jan; Kratochvíl, Jan
3
2006
On the computational complexity of the \(L_{(2,1)}\)-labeling problem for regular graphs. Zbl 1171.68612
Fiala, Jiří; Kratochvíl, Jan
3
2005
Cops, a fast robber and defensive domination on interval graphs. Zbl 1433.91033
Dereniowski, Dariusz; Gavenčiak, Tomáš; Kratochvíl, Jan
1
2019
3-connected reduction for regular graph covers. Zbl 1393.05207
Fiala, Jiří; Klavík, Pavel; Kratochvíl, Jan; Nedela, Roman
2
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
2
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
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áš
6
2017
Extending partial representations of interval graphs. Zbl 1371.05190
Klavík, Pavel; Kratochvíl, Jan; Otachi, Yota; Saitoh, Toshiki; Vyskočil, Tomáš
4
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.
4
2017
Simultaneous orthogonal planarity. Zbl 06687322
Angelini, Patrizio; Chaplick, Steven; Cornelsen, Sabine; Da Lozzo, Giordano; Di Battista, Giuseppe; Eades, Peter; Kindermann, Philipp; Kratochvíl, Jan; Lipp, Fabian; Rutter, Ignaz
3
2016
On the hardness of switching to a small number of edges. Zbl 06622027
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
10
2015
Extending partial representations of subclasses of chordal graphs. Zbl 1311.05133
Klavík, Pavel; Kratochvíl, Jan; Otachi, Yota; Saitoh, Toshiki
5
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
10
2014
Firefighting on square, hexagonal, and triangular grids. Zbl 1301.05241
Gavenčiak, Tomáš; Kratochvíl, Jan; Prałat, Paweł
6
2014
Drawing simultaneously embedded graphs with few bends. Zbl 1426.68212
Grilli, Luca; Hong, Seok-Hee; Kratochvíl, Jan; Rutter, Ignaz
6
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áš
5
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
4
2014
On switching to \(H\)-free graphs. Zbl 1292.05247
Jelínková, Eva; Kratochvíl, Jan
2
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
9
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áš
7
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
Cops and robbers on intersection graphs. Zbl 1329.05209
Gavenčiak, Tomás; Jelínek, Vít; Klavík, Pavel; Kratochvíl, Jan
2
2013
Non-crossing connectors in the plane. Zbl 1382.68264
Kratochvíl, Jan; Ueckerdt, Torsten
1
2013
Cluster vertex deletion: a parameterization between vertex cover and clique-width. Zbl 1365.68278
Doucha, Martin; Kratochvíl, Jan
14
2012
Parameterized complexity of generalized domination problems. Zbl 1241.05108
Golovach, Petr A.; Kratochvíl, Jan; Suchý, Ondřej
7
2012
Extending partial representations of function graphs and permutation graphs. Zbl 1365.05207
Klavík, Pavel; Kratochvíl, Jan; Krawczyk, Tomasz; Walczak, Bartosz
6
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áš
6
2012
Distance three labelings of trees. Zbl 1241.05123
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan; Lidický, Bernard; Paulusma, Daniël
3
2012
Segment representation of a subclass of co-planar graphs. Zbl 1242.05067
Francis, Mathew C.; Kratochvíl, Jan; Vyskočil, Tomáš
2
2012
Extending partial representations of subclasses of chordal graphs. Zbl 1260.68180
Klavík, Pavel; Kratochvíl, Jan; Otachi, Yota; Saitoh, Toshiki
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
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
Parameterized complexity of coloring problems: treewidth versus vertex cover. Zbl 1216.68127
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
19
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
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
On the computational complexity of degenerate unit distance representations of graphs. Zbl 1326.68160
Horvat, Boris; Kratochvíl, Jan; Pisanski, Tomaž
4
2011
Extending partial representations of interval graphs. Zbl 1331.68107
Klavík, Pavel; Kratochvíl, Jan; Vyskočil, Tomáš
3
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
Parameterized problems related to Seidel’s switching. Zbl 1283.68164
Jelinkova, Eva; Suchy, Ondrej; Hlineny, Petr; Kratochvil, Jan
1
2011
Pursuing a fast robber on a graph. Zbl 1192.91027
Fomin, Fedor V.; Golovach, Petr A.; Kratochvíl, Jan; Nisse, Nicolas; Suchan, Karol
28
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
12
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áš
3
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.
38
2009
The capture time of a graph. Zbl 1177.91056
Bonato, A.; Golovach, P.; Hahn, G.; Kratochvíl, J.
24
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áš
12
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
10
2009
Untangling a planar graph. Zbl 1188.05092
Goaoc, Xavier; Kratochvíl, Jan; Okamoto, Yoshio; Shin, Chan-Su; Spillner, Andreas; Wolff, Alexander
9
2009
Parameterized complexity of coloring problems: treewidth versus vertex cover (extended abstract). Zbl 1241.68071
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
6
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
20
2008
Computational complexity of the distance constrained labeling problem for trees (extended abstract). Zbl 1153.68390
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
11
2008
On the computational complexity of partial covers of theta graphs. Zbl 1138.05061
Fiala, Jiří; Kratochvíl, Jan; Pór, Attila
8
2008
Moving vertices to make drawings plane. Zbl 1137.68490
Goaoc, Xavier; Kratochvíl, Jan; Okamoto, Yoshio; Shin, Chan-Su; Wolff, Alexander
4
2008
Intersection graphs of homothetic polygons. Zbl 1267.05177
Kratochvíl, Jan; Pergel, Martin
2
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áš
2
2008
Generalized domination in degenerate graphs: A complete dichotomy of computational complexity. Zbl 1139.68344
Golovach, Petr; Kratochvíl, Jan
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.
8
2007
Exact algorithms for \(L(2,1)\)-labeling of graphs. Zbl 1147.05310
Kratochvíl, Jan; Kratsch, Dieter; Liedloff, Mathieu
8
2007
Computational complexity of generalized domination: A complete dichotomy for chordal graphs. Zbl 1141.68530
Golovach, Petr; Kratochvíl, Jan
5
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.
11
2006
Locally injective graph homomorphism: Lists guarantee dichotomy. Zbl 1167.68406
Fiala, Jiří; Kratochvíl, Jan
9
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.
8
2006
Coloring mixed hypertrees. Zbl 1088.05031
Král, Daniel; Kratochvíl, Jan; Proskurowski, Andrzej; Voss, Heinz-Jürgen
4
2006
Fixed parameter tractability of independent set in segment intersection graphs. Zbl 1154.68428
Kára, Jan; Kratochvíl, Jan
3
2006
Distance constrained labelings of graphs of bounded treewidth. Zbl 1082.68080
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
17
2005
Systems of distant representatives. Zbl 1084.05059
Fiala, Jiří; Kratochvíl, Jan; Proskurowski, Andrzej
14
2005
Computing the branchwidth of interval graphs. Zbl 1084.05068
Kloks, Ton; Kratochvíl, Jan; Müller, Haiko
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 complexity of the balanced vertex ordering problem. Zbl 1128.68402
Kára, Jan; Kratochvíl, Jan; Wood, David R.
2
2005
On the computational complexity of partial covers of theta graphs. Zbl 1203.05152
Fiala, Jiří; Kratochvíl, Jan; Pór, Attila
1
2005
Mixed hypercacti. Zbl 1064.05060
Král’, Daniel; Kratochvíl, Jan; Voss, Heinz-Jürgen
7
2004
Elegant distance constrained labelings of trees. Zbl 1112.68419
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan
2
2004
Two results on intersection graphs of polygons. Zbl 1215.05117
Kratochvíl, Jan; Pergel, Martin
1
2004
Complexity of hypergraph coloring and Seidel’s switching. Zbl 1255.68082
Kratochvíl, Jan
7
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 \(b\)-chromatic number of graphs. Zbl 1024.05026
Kratochvíl, Jan; Tuza, Zsolt; Voigt, Margit
58
2002
On the injective chromatic number of graphs. Zbl 1007.05046
Hahn, Geňa; Kratochvíl, Jan; Širáň, Jozef; Sotteau, Dominique
56
2002
On the complexity of bicoloring clique hypergraphs of graphs. Zbl 1030.68066
Kratochvíl, Jan; Tuza, Zsolt
27
2002
Partial covers of graphs. Zbl 1017.05094
Fiala, Jiří; Kratochvíl, Jan
21
2002
Geometric systems of disjoint representatives. Zbl 1037.68584
Fiala, Jirí; Kratochvíl, Jan; Proskurowski, Andrzej
1
2002
Complexity of coloring graphs without forbidden induced subgraphs. Zbl 1042.68639
Král’, Daniel; Kratochvíl, Jan; Tuza, Zsolt; Woeginger, Gerhard J.
75
2001
Fixed-parameter complexity of \(\lambda\)-labelings. Zbl 0982.05085
Fiala, Jiří; Kloks, Ton; Kratochvíl, Jan
50
2001
Representing graphs by disks and balls (a survey of recognition-complexity results). Zbl 0969.68118
Hliněný, Petr; Kratochvíl, Jan
14
2001
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
Complexity of partial covers of graphs. Zbl 1077.68725
Fiala, Jirí; Kratochvíl, Jan
11
2001
Distance constrained labeling of precolored trees. Zbl 1042.68545
Fiala, Jiří; Kratochvíl, Jan; Proskurowski, Andrzej
10
2001
Independent sets with domination constraints. Zbl 0939.05063
Halldórsson, Magnús M.; Kratochvíl, Jan; Telle, Jan Arne
14
2000
Coloring mixed hypertrees. Zbl 0989.05111
Král, Daniel; Kratochvíl, Jan; Proskurowski, Andrzej; Voss, Heinz-Jürgen
6
2000
Mod-2 independence and domination in graphs. Zbl 1320.05121
Halldórsson, Magnús M.; Kratochvíl, Jan; Telle, Jan Arne
4
2000
New trends in the theory of graph colorings: Choosability and list coloring. Zbl 1025.05030
Kratochvíl, Jan; Tuza, Zsolt; Voigt, Margit
16
1999
Fixed-parameter complexity of \(\lambda\)-labelings. Zbl 0943.05072
Fiala, Jiří; Kloks, Ton; Kratochvíl, Jan
15
1999
New branchwidth territories. Zbl 0924.05063
Kloks, Ton; Kratochvíl, Jan; Müller, Haiko
4
1999
...and 43 more Documents
all top 5

Cited by 1,330 Authors

54 Kratochvíl, Jan
53 Paulusma, Daniël
39 Golovach, Petr A.
22 Chandran, L. Sunil
19 Fiala, Jiří
18 Dourado, Mitre C.
17 Angelini, Patrizio
17 Rzążewski, Paweł
15 Fomin, Fedor V.
14 Král’, Daniel
14 Lozin, Vadim Vladislavovich
14 Ries, Bernard
14 Rutter, Ignaz
13 Liotta, Giuseppe
13 Tuza, Zsolt
12 Da Lozzo, Giordano
12 Frati, Fabrizio
12 Klavík, Pavel
12 Maffray, Frédéric
12 Malyshev, Dmitry S.
12 Sampaio, Rudini Menezes
11 Dabrowski, Konrad Kazimierz
11 Linhares-Sales, Claudia
11 Rautenbach, Dieter
10 Chaplick, Steven
10 Francis, Mathew C.
10 Junosza-Szaniawski, Konstanty
10 Klavžar, Sandi
10 Liedloff, Mathieu
10 Otachi, Yota
10 Song, Jian
10 Telle, Jan Arne
9 Campos, Victor A.
9 Di Battista, Giuseppe
9 Kratsch, Dieter
9 Niedermeier, Rolf
9 Schaudt, Oliver
9 Sivadasan, Naveen
9 Szwarcfiter, Jayme Luiz
9 Van Leeuwen, Erik Jan
9 Zhou, Sanming
8 Bonomo-Braberman, Flavia
8 Bu, Yuehua
8 Cardoso, Domingos Moreira
8 Dantas, Simone
8 Gavenčiak, Tomáš
8 Gavril, Fanica
8 Hell, Pavol
8 Hoàng, Chính T.
8 Lidický, Bernard
8 Montecchiani, Fabrizio
8 Prałat, Paweł
8 Raspaud, André
8 Schäfer, Marcus
7 Bekos, Michael A.
7 Bonato, Anthony
7 Chudnovsky, Maria
7 Di Giacomo, Emilio
7 Esperet, Louis
7 Fulek, Radoslav
7 Kamiński, Marcin Marek
7 Knop, Dušan
7 Liang, Zuosong
7 Ochem, Pascal
7 Ono, Hirotaka
7 Pach, János
7 Protti, Fábio
7 Shan, Erfang
7 Walczak, Bartosz
6 Adiga, Abhijin
6 Broersma, Hajo J.
6 Cameron, Kathie
6 Fellows, Michael Ralph
6 Golumbic, Martin Charles
6 Gonçalves, Daniel
6 Havet, Frédéric
6 Jansen, Bart M. P.
6 Jansen, Klaus
6 Johnson, Matthew
6 Komusiewicz, Christian
6 MacGillivray, Gary
6 Martins, Nicolas A.
6 Milanič, Martin
6 Peterin, Iztok
6 Pinlou, Alexandre
6 Shao, Zhendong
6 Stacho, Juraj
6 Štefankovič, Daniel
6 Stein, Maya Jakobine
6 van ’t Hof, Pim
6 Voigt, Margit
6 Vyskočil, Tomáš
5 Artigas, Danilo
5 Bazgan, Cristina
5 Belmonte, Rémy
5 Bläsius, Thomas
5 Bujtás, Csilla
5 Couturier, Jean-Francois
5 Draque Penso, Lucia
5 Dvořák, Zdeněk
...and 1,230 more Authors
all top 5

Cited in 101 Serials

183 Discrete Applied Mathematics
108 Theoretical Computer Science
105 Discrete Mathematics
55 Algorithmica
43 Information Processing Letters
28 European Journal of Combinatorics
27 Graphs and Combinatorics
21 Journal of Combinatorial Theory. Series B
21 Journal of Combinatorial Optimization
19 Discrete & Computational Geometry
18 Journal of Graph Theory
18 SIAM Journal on Discrete Mathematics
18 Computational Geometry
16 Journal of Graph Algorithms and Applications
15 Journal of Discrete Algorithms
14 Journal of Computer and System Sciences
13 Theory of Computing Systems
10 Discrete Mathematics, Algorithms and Applications
9 Discussiones Mathematicae. Graph Theory
7 Discrete Optimization
6 Combinatorica
6 Information and Computation
6 Annals of Operations Research
6 The Electronic Journal of Combinatorics
5 Linear Algebra and its Applications
5 Combinatorics, Probability and Computing
4 Applied Mathematics and Computation
4 Journal of Combinatorial Theory. Series A
4 Networks
4 Applied Mathematics Letters
4 European Journal of Operational Research
4 Mathematical Programming. Series A. Series B
4 Journal of Mathematical Sciences (New York)
4 Bulletin of the Malaysian Mathematical Sciences Society. Second Series
3 Advances in Mathematics
3 Advances in Applied Mathematics
3 Random Structures & Algorithms
3 CEJOR. Central European Journal of Operations Research
3 Trudy Instituta Matematiki
3 Optimization Letters
2 Acta Informatica
2 Artificial Intelligence
2 Computers & Mathematics with Applications
2 Israel Journal of Mathematics
2 Information Sciences
2 Order
2 Computers & Operations Research
2 International Journal of Foundations of Computer Science
2 Designs, Codes and Cryptography
2 International Journal of Computer Mathematics
2 The Australasian Journal of Combinatorics
2 Opuscula Mathematica
2 Mathematics in Computer Science
2 Algorithms
2 Computer Science Review
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 Pure and Applied Algebra
1 Ricerche di Matematica
1 Siberian Mathematical Journal
1 Transactions of the American Mathematical Society
1 Bulletin of the Korean Mathematical Society
1 Operations Research Letters
1 Bulletin of the Iranian Mathematical Society
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 Applied Mathematical Modelling
1 Journal of the Egyptian Mathematical Society
1 Finite Fields and their Applications
1 Annals of Mathematics and Artificial Intelligence
1 Sbornik: Mathematics
1 International Transactions in Operational Research
1 Journal of Heuristics
1 INFORMS Journal on Computing
1 Mathematical Problems in Engineering
1 Doklady Mathematics
1 Vietnam Journal of Mathematics
1 Taiwanese Journal of Mathematics
1 Annals of Combinatorics
1 Communications of the Korean Mathematical Society
1 Proceedings of the National Academy of Sciences, India. Section A. Physical Sciences
1 Comptes Rendus. Mathématique. Académie des Sciences, Paris
1 South East Asian Journal of Mathematics and Mathematical Sciences
1 4OR
1 Internet Mathematics
1 Journal of Applied Logic
1 AKCE International Journal of Graphs and Combinatorics
1 Acta Universitatis Sapientiae. Informatica
1 Diskretnyĭ Analiz i Issledovanie Operatsiĭ
1 Arabian Journal of Mathematics
1 Journal of the Operations Research Society of China
...and 1 more Serials

Citations by Year

Wikidata Timeline

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