Jan Kratochvíl | Academic Influence

Jan Kratochvíl's AcademicInfluence.com Rankings

Jan Kratochvíl

Computer Science

#2720

World Rank

#2846

Historical Rank

Database

#8049

World Rank

#8388

Historical Rank

computer-science Degrees

Download Badge

Computer Science

Jan Kratochvíl's Degrees

PhD Computer Science Charles University

Similar Degrees You Can Earn

Best Online PhD of Computer Science (Doctorates) 2025

Why Is Jan Kratochvíl Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Jan Kratochvíl is a Czech mathematician and computer scientist whose research concerns graph theory and intersection graphs. Kratochvíl was born on 10 February 1959 in Prague. He studied at Charles University in Prague, earning a master's degree in 1983 and a Ph.D. in 1987; his dissertation, supervised by Jaroslav Nešetřil, combined graph theory with coding theory. He remained at Charles University as a faculty member, earned his habilitation in 1995, and was promoted to full professor in 2003. From 2003 to 2011 he chaired the department of applied mathematics at Charles University, and from 2012 to 2020 he was the dean of the Faculty of Mathematics and Physics there.

(See a Problem?)

Jan Kratochvíl's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

A Special Planar Satisfiability Problem and a Consequence of Its NP-completeness (1994) (207)
Complexity of Coloring Graphs without Forbidden Induced Subgraphs (2001) (203)
Intersection Graphs of Segments (1994) (181)
String graphs. II. recognizing string graphs is NP-hard (1991) (165)
On the b-Chromatic Number of Graphs (2002) (139)
On the injective chromatic number of graphs (2002) (127)
Covering and coloring polygon-circle graphs (1997) (105)
Testing planarity of partially embedded graphs (2010) (93)
String graphs requiring exponential representations (1991) (93)
Representing graphs by disks and balls (a survey of recognition-complexity results) (2001) (89)
On the computation of the hull number of a graph (2009) (84)
Algorithmic complexity of list colorings (1994) (83)
Parameterized complexity of coloring problems: Treewidth versus vertex cover (2009) (82)
Fixed-Parameter Complexity of lambda-Labelings (1999) (82)
Pursuing a fast robber on a graph (2010) (78)
One More Occurrence of Variables Makes Satisfiability Jump From Trivial to NP-Complete (1993) (78)
Independent Sets with Domination Constraints (1998) (76)
The Inflation of the Margin of Appreciation by the European Court of Human Rights (2011) (75)
The capture time of a graph (2009) (75)
On the complexity of bicoloring clique hypergraphs of graphs (extended abstract) (2000) (70)
New trends in the theory of graph colorings: Choosability and list coloring (1997) (67)
The complexity of induced minors and related problems (1995) (66)
Perfect codes over graphs (1986) (64)
Mathematical Foundations of Computer Science 2004 (2004) (63)
Locally constrained graph homomorphisms - structure, complexity, and applications (2008) (55)
Topics in Discrete Mathematics (2006) (52)
Partial covers of graphs (2002) (50)
Distance Constrained Labelings of Graphs of Bounded Treewidth (2005) (50)
Covering Regular Graphs (1997) (49)
String graphs. I. The number of critical nonstring graphs is infinite (1991) (48)
Noncrossing Subgraphs in Topological Layouts (1991) (44)
Max-tolerance graphs as intersection graphs: cliques, cycles, and recognition (2006) (42)
On the Complexity of Graph Covering Problems (1998) (41)
Exact Algorithms for L(2,1)-Labeling of Graphs (2011) (40)
A kuratowski-type theorem for planarity of partially embedded graphs (2011) (40)
On Restricted Two-Factors (1988) (40)
On the Computational Complexity of Codes in Graphs (1988) (39)
Systems of distant representatives (2005) (37)
Brooks-type theorems for choosability with separation (1998) (36)
Extending Partial Representations of Subclasses of Chordal Graphs (2012) (36)
Extending Partial Representations of Proper and Unit Interval Graphs (2012) (34)
The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree (2009) (34)
Coloring precolored perfect graphs (1997) (34)
Complexity of Partial Covers of Graphs (2001) (34)
Precoloring extension with fixed color bound. (1993) (33)
Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width (2012) (33)
On tractability of Cops and Robbers game (2008) (32)
Coloring Mixed Hypertrees (2000) (32)
Extending Partial Representations of Function Graphs and Permutation Graphs (2012) (32)
Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill (2012) (32)
On the Computational Complexity of Seidel's Switching (1992) (31)
Efficient algorithms for graphs with few P4's (2001) (31)
NP-hardness results for intersection graphs (1989) (29)
Clustered Planarity: Small Clusters in Cycles and Eulerian Graphs (2009) (29)
Intersection Graphs of Noncrossing Arc-Connected Sets in the Plane (1996) (28)
Clustered Planarity: Embedded Clustered Graphs with Two-Component Clusters (2009) (28)
Extending Partial Representations of Interval Graphs (2011) (28)
Complexity of Hypergraph Coloring and Seidel's Switching (2003) (27)
Homothetic Triangle Contact Representations of Planar Graphs (2007) (25)
Distance Constrained Labeling of Precolored Trees (2001) (25)
Contact Representations of Planar Graphs: Extending a Partial Representation is Hard (2014) (25)
Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract) (2008) (24)
On the computational complexity of partial covers of Theta graphs (2005) (23)
Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy (2006) (23)
Parameterized complexity of generalized domination problems (2009) (22)
On the Complexity of the Balanced Vertex Ordering Problem (2005) (22)
Thresholds for classes of intersection graphs (1992) (21)
On intersection representations of co-planar graphs (1998) (20)
Mod-2 Independence and Domination in Graphs (1999) (20)
Planar Graph Coloring Avoiding Monochromatic Subgraphs: Trees and Paths Make It Difficult (2006) (20)
Fast exact algorithm for L(2, 1)-labeling of graphs (2011) (18)
Satisfiability of co-nested formulas (1993) (18)
Generalized Domination in Chordal Graphs (1995) (17)
Algorithms and Characterizations for 2-Layer Fan-planarity: From Caterpillar to Stegosaurus (2015) (17)
Mixed hypercacti (2004) (17)
Mixed hypergraphs with bounded degree: edge-coloring of mixed multigraphs (2003) (16)
New Branchwidth Territories (1999) (16)
Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs (2014) (15)
Crossing Number of Abstract Topological Graphs (1998) (15)
Computing the branchwidth of interval graphs (2005) (15)
Hom-properties are uniquely factorizable into irreducible factors (2000) (15)
Complexity of Colored Graph Covers I. Colored Directed Multigraphs (1997) (14)
Drawing Simultaneously Embedded Graphs with Few Bends (2014) (14)
On the computational complexity of (O, P)-partition problems (1997) (14)
A note on planar partial 3-trees (2012) (13)
Intersection graphs of homothetic polygons (2008) (13)
Moving Vertices to Make Drawings Plane (2007) (13)
Firefighting on square, hexagonal, and triangular grids (2013) (13)
Parameterized Problems Related to Seidel's Switching (2011) (13)
Fixed Parameter Tractability of Independent Set in Segment Intersection Graphs (2006) (13)
Intersection Dimensions of Graph Classes (1994) (12)
Cops and Robbers on Intersection Graphs (2013) (12)
Computational Complexity of the Krausz Dimension of Graphs (1997) (12)
Clustered Planarity: Small Clusters in Eulerian Graphs (2007) (12)
Distance three labelings of trees (2012) (11)
Graphs maximal with respect to hom-properties (1997) (11)
Exact Algorithms for L (2, 1)-Labeling of Graphs (2007) (11)
Complexity of choosing subsets from color sets (1998) (11)
On the complexity of reconstructing H‐free graphs from their Star Systems (2011) (10)
Transversal Partitioning in Balanced Hypergraphs (1997) (10)
Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems - (Extended Abstract) (2015) (10)
On the Computational Complexity of the L(2, 1)-Labeling Problem for Regular Graphs (2005) (10)
Parameterized complexity of distance labeling and uniform channel assignment problems (2017) (9)
3-connected Reduction for Regular Graph Covers (2015) (9)
Branch and Recharge: Exact Algorithms for Generalized Domination (2007) (9)
Simultaneous Orthogonal Planarity (2016) (9)
Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs (2007) (9)
Geometric Intersection Graphs: Do Short Cycles Help? (2007) (9)
Linear-time Algorithm for Partial Representation Extension of Interval Graphs (2013) (8)
On the Computational Complexity of Degenerate Unit Distance Representations of Graphs (2010) (8)
Distance Constrained Labelings of Trees (2008) (8)
Rankings of Directed Graphs (1998) (8)
On Switching to H‐Free Graphs (2014) (8)
On the number of Hamiltonian cycles in triangulations (1988) (8)
Sort and Search: Exact algorithms for generalized domination (2009) (7)
Determining the L(2, 1)-Span in Polynomial Space (2012) (7)
Non-crossing Connectors in the Plane (2012) (7)
U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited (2020) (7)
Planar Embeddings with Small and Uniform Faces (2014) (7)
Algorithmic Aspects of Regular Graph Covers (2016) (7)
Two Results on Intersection Graphs of Polygons (2003) (7)
Web Usage Mining: Data Pre-processing Impact on Found Knowledge in Predictive Modelling (2020) (6)
Grid Intersection and Box Intersection Graphs on Surfaces (Extended Abstract) (1995) (6)
Segment representation of a subclass of co-planar graphs (2010) (6)
Elegant Distance Constrained Labelings of Trees (2004) (5)
Cops, a fast robber and defensive domination on interval graphs (2019) (5)
Realizing a Promise: A Case for Ratification of theOptional Protocol to the Covenant on Economic, Social and Cultural Rights (2009) (5)
Beyond Homothetic Polygons: Recognition and Maximum Clique (2012) (5)
Disjoint and unfolding domination in graphs (1998) (5)
Compatible 2-factors (1992) (4)
Computational complexity of covering three-vertex multigraphs (2014) (4)
Complexity Note on Mixed Hypergraphs (2001) (4)
Planar Graph Coloring with Forbidden Subgraphs: Why Trees and Paths Are Dangerous (2002) (4)
Geometric Systems of Disjoint Representatives (2002) (4)
1-perfect codes over self-complementary graphs (1985) (4)
Graph Drawing: 7th International Symposium, GD’99 Štiřín Castle, Czech Republic September 15–19, 1999 Proceedings (1999) (4)
Regular codes in regular graphs are difficult (1994) (4)
Locally injective k-colourings of planar graphs (2014) (3)
On Vertex- and Empty-Ply Proximity Drawings (2017) (3)
On the Hardness of Switching to a Small Number of Edges (2016) (3)
Determining the L(2, 1)L(2, 1)-span in polynomial space (2011) (3)
Cops and Robbers on String Graphs (2015) (3)
Matching and l-Subgraph Contractibility to Planar Graphs (2012) (3)
Faithful Representations of Graphs by Islands in the Extended Grid (2010) (3)
On Switching to H-Free Graphs (2008) (3)
Generalized Domination in Degenerate Graphs: A Complete Dichotomy of Computational Complexity (2008) (3)
Edge decompositions of multigraphs into multi-2-paths (2004) (3)
Bounded Stub Resolution for Some Maximal 1-Planar Graphs (2018) (2)
Homothetic polygons and beyond: Maximal cliques in intersection graphs (2018) (2)
Collection of Abstracts (2011) (2)
Proportional Graphs (1991) (2)
Combinatorial Algorithms, 20th International Workshop, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28-July 2, 2009, Revised Selected Papers (2009) (2)
Completion of the mixed unit interval graphs hierarchy (2014) (2)
On the Complexity of Reconstructing H -free Graphs from Their Star Systems (2008) (2)
On Hamiltonian cycles in two-triangle graphs (1987) (2)
Structural decompositions, width parameters, and graph labelings (2005) (1)
Homothetic Polygons and Beyond: Intersection Graphs, Recognition, and Maximum Clique (2014) (1)
Firefighting on square and hexagonal grids (2013) (1)
Computational Complexity of Covering Two-vertex Multigraphs with Semi-edges (2021) (1)
Perfect codes in graphs and their Cartesian powers [Abstract of thesis] (1989) (1)
The Stub Resolution of 1-Planar Graphs (2020) (1)
The Right to Life in the Perspective of the Human Rights Committee and the European Court of Human Rights (2006) (1)
MSOL Restricted Contractibility to Planar Graphs (2012) (1)
Combinatorial Algorithms : 25th International Workshop, IWOCA 2014, Duluth, MN, USA, October 15-17, 2014, Revised Selected Papers (2015) (1)
Distance constrained labeling on graphs with bounded neighborhood diversity (2015) (1)
Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Teplá Monastery, Czech Republic, June 21-24, 2011. Revised Papers (2011) (1)
Extending Partial Representations of Proper and Unit Interval Graphs (2016) (1)
Computational Complexity of Covering Multigraphs with Semi-Edges: Small Cases (2021) (1)
Computational Complexity of Covering Disconnected Multigraphs (2021) (1)
The Rique-Number of Graphs (2022) (1)
Can they cross? and how?: (the hitchhiker's guide to the universe of geometric intersection graphs) (2011) (1)
Branch and Recharge: Exact Algorithms for Generalized Domination (2011) (1)
Proceedings of the 7th International Symposium on Graph Drawing (1999) (1)
Preface (2013) (0)
Special Issue on Selected Papers from the Seventh International Symposium on Graph Drawing, GD'99 – : Guest Editors' Foreword (2004) (0)
Proceedings of the 37th international conference on Graph-Theoretic Concepts in Computer Science (2011) (0)
Complexity of Locally Injective k-Colourings of Planar Graphs (2013) (0)
Guest Editors' Foreword (2010) (0)
Proceedings of the 7th annual conference on Theory and Applications of Models of Computation (2010) (0)
Graph Covers: Where Topology Meets Computer Science, and Simple Means Difficult (2023) (0)
Mathematical Foundations of Computer Science 2004: 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004, Proceedings (Lecture Notes in Computer Science) (2004) (0)
Preface (2010) (0)
Extending Partial Representations of Interval Graphs (2016) (0)
Guest editors' foreword (2009) (0)
List covering of regular multigraphs (2022) (0)
Preface (2013) (0)
Preface (2005) (0)
Subsidiarity of Human Rights in Practice: The relationship between the Constitutional Court and Lower Courts in Czechia (2019) (0)
Editorial (2007) (0)
Preface (2013) (0)
Preface (2007) (0)
Booms and Busts in Prague’s Commercial Real Estate Market (2014) (0)
Guest Editors' Foreword (2002) (0)
Theory and Applications of Models of Computation, 7th Annual Conference, TAMC 2010, Prague, Czech Republic, June 7-11, 2010. Proceedings (2010) (0)
263 k-Ramsey classes and dimensions of graphs (2012) (0)
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) (2001) (0)
$k$-Ramsey classes and dimensions of graphs (1995) (0)
Guest editors' foreword (2012) (0)
Foreword (2001) (0)
Updates from the Regional Human Rights Systems (2009) (0)
Induced minors and related problems (1991) (0)
A Model of Microstructure Evolution in Metals Exposed to Large Strains (2018) (0)
III. odboj v Československu z pohledu hodnot EPP-ED : IIIrd resistance in Czechoslovakia from the view of EPP-ED values. (2006) (0)
The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree (2012) (0)
Guest editors' foreword (2014) (0)
Humanitarian Intervention and State Responsibility (2007) (0)
Preface: Ninth workshop on graph classes, optimization, and Width Parameters, Vienna, Austria (2022) (0)

This paper list is powered by the following services:

Other Resources About Jan Kratochvíl

en.wikipedia.org

What Schools Are Affiliated With Jan Kratochvíl?

Jan Kratochvíl is affiliated with the following schools:

Charles University

Image Attributions

Image Source for Jan Kratochvíl