hlavni banner

kudy kam

Jan Kratochvil's Research

photo JK

My main research areas are Graph Theory and Combinatorics, studied in algorithmic and computational complexity point of views. In these areas I coauthored over 100 research papers (easiest seen at dblp ), which acquired over 1850 citations (according to WOS in July, 2022). The topics I enjoyed working on include

  • Graph Drawing and Geometric Intersection Graphs, currently in the focus of EUROCORES Collaborative Research Project GraDR EUROGIGA
  • Graph Covers - Locally constrained graph homomorphisms, partial covers and their computational complexity issues. With Roman Nedela and Jozef Siran we established a series of workshops ATCAGC (Algebraic, Topological and Complexity Aspects of Graph Covers). talk at MCW 2021
  • Distance Constrained Graph Labeling - stemming from the Frequence Assignment Problem. With J. Fiala and P. Golovach we showed that the L(2,1)-labeling problem is NP-complete for series parallel graphs and the L(p,q)-labeling one even for trees (if q>1 and relatively prime to p).
  • Domination theory and perfect codes in graphs. Exact exponantial time algorithms for these problems.
  • Graph Colorings - complexity of precoloring extension problems, list colorings, choosability, binding functions for chromatic number for special classes of graphs.

Guest Editted Special Issues and Refereed Conference Proceedings

  • Contemporary Trends in Discrete Mathematics (from DIMACS and DIMATIA to the future) (R.L.Graham, J.Kratochvil, J.Nesetril, F.S.Roberts, eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 49, American Mathematical Society, Providence, RI, 1999, ISBN 0-8218-0963-6
  • Graph Drawing, Proceedings of the 7th international Symposium on Graph Drawing, Stirin castle, September 1999, LNCS 1731, Springer-Verlag, 1999
  • Combinatorics, Graph Theory, Algorithms and Applications (guest editors M.Fiedler, J.Kratochvil, J.Nesetril), Discrete Mathematics 229, Elsevier, 2001
  • Graph Theory (guest editors M.Fiedler, J.Kratochvil, J.Nesetril), Discrete Mathematics 233, Elsevier, 2001
  • Combinatorics (guest editors M.Fiedler, J.Kratochvil, J.Nesetril), Discrete Mathematics 235, Elsevier, 2001
  • Graph Drawing and Representations: Special Issue on Selected papers from 1999 Symposium on Graph Drawing, Journal of Graph Algorithms and Applications, Vol. 6, No. 1, 2002 (guest editors Hubert de Fraysseix and Jand Kratochvil), guest editors' foreward JGAA 6 (2002), 3-5
  • Mathematical Foundations of Computer Science (J. Fiala, V. Koubek, J. Kratochvil, eds.), LNCS 3153, Springer Verlag, 2004, 902 pp.
  • Structural decompositions, width Parameters and Graph Labelings, special issue of Discrete Applied Mathematics Vol 145, Issue 2, 2005 (guest editors Jan Kratochvil, Andrzej Proskurowski, Oriol Serra), Editorial DAM 145 (2005) 141-142, Elsevier, 2005
  • Mathematical Foundations of Computer Science 2004, special issues of Theoretical Computer Science 345, Issues 2-3, 2005 (guest editors V. Koubek and J. Kratochvil), Editorial TCS 345 (2005) 171-2, Elsevier, 2005
  • Topics in Discrete Mathematics, Dedicated to Jarik Nesetril on the Occasion of his 60th Birthday (M. Klazar, J. Kratochvil, M. Loebl, J. Matousek, R. Thomas and P. Valtr, eds.), Algorithms and Combinatorics 26, Springer-Verlag, 2006, 627 pp., ISBN 978-3-540-33698-3
  • 29th Symposium on Mathematical Foundations of Computer Science MFCS 2004, special issue of Discrete App. Math. 155, Issue 2, 2007 (guest editors J. Kratochvil, J. Diaz, J. Fiala), Editorial DAM 155 (2007), 79-80, Elsevier, 2007, 178 pages
  • Second Workshop on Graph Classes, Optimization, and Width Parameters, special issue of Discrete Appl. Math. 157, Issue 12, 2009 (guest editors J. Kratochvil, A. Proskurowski, O. Serra), Guest Edeitors' Foreword DAM 157 (2009), 2575-2576, Elsevier, 2009, 187 pages
  • Combinatorial Algorithms, 20th International Workshop, IWOCA 2009 (guest eds. J. Fiala, J. Kratochvil, M. Miller), LNCS 5874, Springer 2009, 477 pages
  • Third Workshop on Graph Classes, Optimization, and Width Parameters, Eugene, Oregon, USA, October 2007, special issue of Discrete Appl. Math. 158, Issue 7, 2010 (guest editors P. Heggernes, J. Kratochvil, A. Proskurowski), Guest Editors' Foreword DAM 158 (2010), 729-730, Elsevier, 2010, 139 pages
  • Sixth Czech-Slovak International Symposium on Cobinatorics, Graph Thoery, Algorithms and Applications, special issue of Discrete Math. 310, Issue 3, 2010 (guest editors J. Kratochvil, J. Nesetril, Z. Ryjacek), Guest Editors' Foreword DM 310 (2010), 371-372, Elsevier, 2010, 299 pages.
  • Theory and Applications of Models of Computation, 7th Annual Conference, TAMC 2010, Prague, Czech Republic, June 7-11, 2010. Proceedings (Jan Kratochvíl, Angsheng Li, Jirí Fiala, Petr Kolman, eds.), LNCS 6108, Springer 2010, 478 pages.
  • Graph-Theoretic Concepts in Computer Science, 37th International Workshop, WG 2011, Teplá Monastery, Czech Republic, June 21-24, 2011. Proceedings (Petr Kolman, Jan Kratochvil, eds.), LNCS 6986, Springer 2011, 342 pages.
  • Fourth Workshop on Graph Classes, Optimization, and Width Parameters, Bergen, Norway, October 2009, special issue of Discrete Appl. Math. 160, Issue 6, 2012 (guest editors P. Heggernes, J. Kratochvil, A. Proskurowski), Guest Editors' Foreword DAM 160 (2012), 683-684, Elsevier, 2012, 241 pages.
  • Combinatorics and Stringology, special issue of European Journal of Combinatorics 34, issue 1, 2013 (guest editors Jan Kratochvil and Mirka Miller), Preface 1-2, Elsevier 2013, 154 pages.
  • Combinatorial Algorithms and Complexity, special issue of European Journal of Combinatoric s 34, issue 3, 2013 (guest editors Jan Kratochvil and Mirka Miller), Preface 539-540, Elsevier 2013, 163 pages.
  • Fifth Workshop on Graph Classes, Optimization, and Width Parameters, Daejon, Korea, October 20011, special issue of Discrete Appl. Math. 168, 2014 (guest editors P. Heggernes, J. Kratochvil, S. Oum), Guest Editors' Foreword DAM 168 (2014), 1-2, Elsevier, 2014, 126 pages.
  • Combinatorial Algorithms, 25th International Workshop, IWOCA 2014, Duluth, USA, October 15-17, 2014, Revised Selected Papers (J. Kratochvil, M. Miller, D. Froncek, eds.), LNCS 8986, Springer 2015, 375 pages.
  • Combinatorial Algorithms, Dedicated to the Memory of Mirka Miller, special issue of European Journal of Combinatorics, Vol. 68, February 2018 (Guest editors Jan Kratochvil, Mirka Miller, Zsuzsanna Liptak), Guest Editors' Preface EJC 68 (2018) 1-2
  • Robert Ganian, Jan Kratochvíl, Stefan Szeider: Ninth workshop on graph classes, optimization, and Width Parameters, Vienna, Austria. Discret. Appl. Math. 312: 1-2 (2022)

Selected Invited Talks

  • "Graph Covers: Where Topology Meets Computer Science, and Simple Means Difficult", WALCOM 2023, Hsinchu, March 2023
  • "Geometric Intersection Graphs", IWCIA 2018, Porto, November 2018
  • "Cops and Robbers on Geometric Intersection Graphs", GRASCan 2017, Corner Brook, August 2017
  • "Domination in Graphs: Old, New, Borrowed and Blue, A Tribute to Mirka Miller", DiG2016, Ubud, Indonesia, July 2016
  • "Interval Graphs. Such an old stuff. Can there still be anything new to talk about?", 3-in-1 Workshop, Krynica, November 2015
  • "Extending Partial Geometric Representationsf Graphs", 7th Cracow Conference on Graph Theory, 7CCGT, Rytro, September 2014
  • "Extending partial representations of graphs", 2nd Bordeaux Graph Workshop, BGW 2012, November 2012
  • "Geometric Intersection Graphs: Old Problems, New Approaches (and Vice Versa)", 28th European Workshop on Computational Geometry, EuroCG 2012, Assisi, February 2012
  • "Can they cross? And how?", 27th Annual Symposium on Computational Geometry, SoCG 2011, Paris, June 2011
  • "Distance Constrained Graph Labelings: From Frequency Assignment to Graph Homomorphisms", 13th Workshop on Graph Theory, CID '09 , Szklarska Poreba, September 2009
  • "Geometric intersection graphs", 2nd Polish Combinatorial Conference, Bedlewo, November 2008
  • "Generalized domination in special graph classes", Graph Theory 2008 at Sandbjerg Manor, Honoring the 60th Birthday of Cartsen Thomassen, August 2008
  • "Geometric intersection graphs", New Directions in Algorithms, Combinatorics, and Optimization, Honoring 65th Birthday of Tom Trotter, Atlanta, May 2008
  • "Locally constrained graph homomorphisms", EUROCOMB '07, Sevilla, September 2007
  • "Geometric intersection graphs - a survey", 6th Slovenian International Conference on Graph Theory, Bled, June 2007

Publications

See dblp or ORCID.

Links to talks

poslední aktualizace 24. 2. 2013

© m@f# for contents, RooT for design