Bok, Jan; Fiala, Jiří; Jedličková, Nikola; Kratochvíl, Jan; Rzążewski, Paweł List covering of regular multigraphs with semi-edges. (English) Zbl 07823158 Algorithmica 86, No. 3, 782-807 (2024). MSC: 68Wxx 05Cxx PDFBibTeX XMLCite \textit{J. Bok} et al., Algorithmica 86, No. 3, 782--807 (2024; Zbl 07823158) Full Text: DOI
Kratochvíl, Jan Graph covers: where topology meets computer science, and simple means difficult. (English) Zbl 07770276 Lin, Chun-Cheng (ed.) et al., WALCOM: algorithms and computation. 17th international conference and workshops, WALCOM 2023, Hsinchu, Taiwan, March 22–24, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13973, 3-11 (2023). MSC: 68Wxx PDFBibTeX XMLCite \textit{J. Kratochvíl}, Lect. Notes Comput. Sci. 13973, 3--11 (2023; Zbl 07770276) Full Text: DOI
Grilli, Luca; Hong, Seok-Hee; Kratochvíl, Jan; Rutter, Ignaz Drawing simultaneously embedded graphs with few bends. (English) Zbl 1527.05126 Int. J. Found. Comput. Sci. 34, No. 7, 807-824 (2023). Reviewer: Ioan Tomescu (Bucureşti) MSC: 05C62 68R10 68Q17 PDFBibTeX XMLCite \textit{L. Grilli} et al., Int. J. Found. Comput. Sci. 34, No. 7, 807--824 (2023; Zbl 1527.05126) Full Text: DOI
Bekos, Michael A.; Felsner, Stefan; Kindermann, Philipp; Kobourov, Stephen; Kratochvíl, Jan; Rutter, Ignaz The Rique-number of graphs. (English) Zbl 07727774 Angelini, Patrizio (ed.) et al., Graph drawing and network visualization. 30th international symposium, GD 2022, Tokyo, Japan, September 13–16, 2022. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 13764, 371-386 (2023). MSC: 68R10 68U05 PDFBibTeX XMLCite \textit{M. A. Bekos} et al., Lect. Notes Comput. Sci. 13764, 371--386 (2023; Zbl 07727774) Full Text: DOI arXiv
Bok, Jan; Fiala, Jiří; Jedličková, Nikola; Kratochvíl, Jan; Rzążewski, Paweł List covering of regular multigraphs. (English) Zbl 07577702 Bazgan, Cristina (ed.) et al., Combinatorial algorithms. 33rd international workshop, IWOCA 2022, Trier, Germany, June 7–9, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13270, 228-242 (2022). MSC: 68Rxx 68Wxx PDFBibTeX XMLCite \textit{J. Bok} et al., Lect. Notes Comput. Sci. 13270, 228--242 (2022; Zbl 07577702) Full Text: DOI arXiv
Ganian, Robert (ed.); Kratochvíl, Jan (ed.); Szeider, Stefan (ed.) Preface: Ninth workshop on graph classes, optimization, and width parameters, Vienna, Austria. (English) Zbl 1484.00103 Discrete Appl. Math. 312, 1-2 (2022). MSC: 00B15 00B25 05-06 68-06 PDFBibTeX XMLCite \textit{R. Ganian} (ed.) et al., Discrete Appl. Math. 312, 1--2 (2022; Zbl 1484.00103) Full Text: DOI
Kaufmann, Michael; Kratochvil, Jan; Lipp, Fabian; Montecchiani, Fabrizio; Raftopoulou, Chrysanthi; Valtr, Pavel The stub resolution of 1-planar graphs. (English) Zbl 1489.05030 J. Graph Algorithms Appl. 25, No. 2, 625-642 (2021). MSC: 05C10 05C62 68R10 PDFBibTeX XMLCite \textit{M. Kaufmann} et al., J. Graph Algorithms Appl. 25, No. 2, 625--642 (2021; Zbl 1489.05030) Full Text: DOI
Kratochvíl, Jan; Masařík, Tomáš; Novotná, Jana \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited. (English) Zbl 1518.68270 Algorithmica 83, No. 12, 3649-3680 (2021). MSC: 68R10 05C62 05C85 68Q25 PDFBibTeX XMLCite \textit{J. Kratochvíl} et al., Algorithmica 83, No. 12, 3649--3680 (2021; Zbl 1518.68270) Full Text: DOI arXiv
Kratochvíl, Jan; Masařík, Tomáš; Novotná, Jana U-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited. (English) Zbl 1518.68271 Esparza, Javier (ed.) et al., 45th international symposium on mathematical foundations of computer science, MFCS 2020, August 25–26, 2020, Prague, Czech Republic. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 170, Article 57, 14 p. (2020). MSC: 68R10 05C62 05C85 68Q25 PDFBibTeX XMLCite \textit{J. Kratochvíl} et al., LIPIcs -- Leibniz Int. Proc. Inform. 170, Article 57, 14 p. (2020; Zbl 1518.68271) Full Text: DOI
Kaufmann, Michael; Kratochvil, Jan; Lipp, Fabian; Montecchiani, Fabrizio; Raftopoulou, Chrysanthi; Valtr, Pavel The stub resolution of 1-planar graphs. (English) Zbl 07224282 Rahman, M. Sohel (ed.) et al., WALCOM: algorithms and computation. 14th international conference, WALCOM 2020, Singapore, Singapore, March 31 – April 2, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12049, 170-182 (2020). MSC: 68Wxx PDFBibTeX XMLCite \textit{M. Kaufmann} et al., Lect. Notes Comput. Sci. 12049, 170--182 (2020; Zbl 07224282) Full Text: DOI
Angelini, Patrizio; Chaplick, Steven; De Luca, Felice; Fiala, Jiří; Hančl, Jaroslav jun.; Heinsohn, Niklas; Kaufmann, Michael; Kobourov, Stephen; Kratochvíl, Jan; Valtr, Pavel On vertex- and empty-ply proximity drawings. (English) Zbl 1503.68202 Frati, Fabrizio (ed.) et al., Graph drawing and network visualization. 25th international symposium, GD 2017, Boston, MA, USA, September 25–27, 2017. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 10692, 24-37 (2018). MSC: 68R10 68U05 PDFBibTeX XMLCite \textit{P. Angelini} et al., Lect. Notes Comput. Sci. 10692, 24--37 (2018; Zbl 1503.68202) Full Text: DOI arXiv
Kaufmann, Michael; Kratochvíl, Jan; Lipp, Fabian; Montecchiani, Fabrizio; Raftopoulou, Chrysanthi; Valtr, Pavel Bounded stub resolution for some maximal 1-planar graphs. (English) Zbl 1497.68384 Panda, B. S. (ed.) et al., Algorithms and discrete applied mathematics. 4th international conference, CALDAM 2018, Guwahati, India, February 15–17, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10743, 214-220 (2018). MSC: 68R10 05C10 05C85 PDFBibTeX XMLCite \textit{M. Kaufmann} et al., Lect. Notes Comput. Sci. 10743, 214--220 (2018; Zbl 1497.68384) Full Text: DOI
Abello, James; Klavík, Pavel; Kratochvíl, Jan; Vyskočil, Tomáš MSOL restricted contractibility to planar graphs. (English) Zbl 1370.68113 Theor. Comput. Sci. 676, 1-14 (2017). MSC: 68Q25 05C10 05C62 05C85 68R10 PDFBibTeX XMLCite \textit{J. Abello} et al., Theor. Comput. Sci. 676, 1--14 (2017; Zbl 1370.68113) Full Text: DOI
Angelini, Patrizio; Chaplick, Steven; Cornelsen, Sabine; Da Lozzo, Giordano; Di Battista, Giuseppe; Eades, Peter; Kindermann, Philipp; Kratochvíl, Jan; Lipp, Fabian; Rutter, Ignaz Simultaneous orthogonal planarity. (English) Zbl 1478.68211 Hu, Yifan (ed.) et al., Graph drawing and network visualization. 24th international symposium, GD 2016, Athens, Greece, September 19–21, 2016. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 9801, 532-545 (2016). MSC: 68R10 05C10 68Q17 68Q25 PDFBibTeX XMLCite \textit{P. Angelini} et al., Lect. Notes Comput. Sci. 9801, 532--545 (2016; Zbl 1478.68211) Full Text: DOI arXiv
Jelínek, Vít; Jelínková, Eva; Kratochvíl, Jan On the hardness of switching to a small number of edges. (English) Zbl 1477.68232 Dinh, Thang N. (ed.) et al., Computing and combinatorics. 22nd international conference, COCOON 2016, Ho Chi Minh City, Vietnam, August 2–4, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9797, 159-170 (2016). MSC: 68R10 05C42 05C76 68Q17 68Q25 PDFBibTeX XMLCite \textit{V. Jelínek} et al., Lect. Notes Comput. Sci. 9797, 159--170 (2016; Zbl 1477.68232) Full Text: DOI arXiv
Fiala, Jiří; Gavenčiak, Tomáš; Knop, Dušan; Koutecký, Martin; Kratochvíl, Jan Fixed parameter complexity of distance constrained labeling and uniform channel assignment problems (extended abstract). (English) Zbl 1476.68207 Dinh, Thang N. (ed.) et al., Computing and combinatorics. 22nd international conference, COCOON 2016, Ho Chi Minh City, Vietnam, August 2–4, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9797, 67-78 (2016). MSC: 68R10 05C78 68Q27 PDFBibTeX XMLCite \textit{J. Fiala} et al., Lect. Notes Comput. Sci. 9797, 67--78 (2016; Zbl 1476.68207) Full Text: DOI arXiv
Angelini, Patrizio; Di Battista, Giuseppe; Frati, Fabrizio; Jelínek, Vít; Kratochvíl, Jan; Patrignani, Maurizio; Rutter, Ignaz Testing planarity of partially embedded graphs. (English) Zbl 1398.68385 ACM Trans. Algorithms 11, No. 4, Article No. 32, 42 p. (2015). MSC: 68R10 05C10 05C85 68Q25 PDFBibTeX XMLCite \textit{P. Angelini} et al., ACM Trans. Algorithms 11, No. 4, Article No. 32, 42 p. (2015; Zbl 1398.68385) Full Text: DOI
Binucci, Carla; Chimani, Markus; Didimo, Walter; Gronemann, Martin; Klein, Karsten; Kratochvíl, Jan; Montecchiani, Fabrizio; Tollis, Ioannis G. 2-layer fan-planarity: from caterpillar to stegosaurus. (English) Zbl 1471.68187 Di Giacomo, Emilio (ed.) et al., Graph drawing and network visualization. 23rd international symposium, GD 2015, Los Angeles, CA, USA, September 24–26, 2015. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 9411, 281-294 (2015). MSC: 68R10 05C10 05C62 PDFBibTeX XMLCite \textit{C. Binucci} et al., Lect. Notes Comput. Sci. 9411, 281--294 (2015; Zbl 1471.68187) Full Text: DOI Link
Kratochvíl, Jan (ed.); Miller, Mirka (ed.); Froncek, Dalibor (ed.) Combinatorial algorithms. 25th international workshop, IWOCA 2014, Duluth, MN, USA, October 15–17, 2014. Revised selected papers. (English) Zbl 1318.68027 Lecture Notes in Computer Science 8986. Cham: Springer (ISBN 978-3-319-19314-4/pbk; 978-3-319-19315-1/ebook). xiii, 377 p. (2015). MSC: 68-06 68Rxx 68Wxx 00B25 PDFBibTeX XMLCite \textit{J. Kratochvíl} (ed.) et al., Combinatorial algorithms. 25th international workshop, IWOCA 2014, Duluth, MN, USA, October 15--17, 2014. Revised selected papers. Cham: Springer (2015; Zbl 1318.68027) Full Text: DOI
Da Lozzo, Giordano; Jelínek, Vít; Kratochvíl, Jan; Rutter, Ignaz Planar embeddings with small and uniform faces. (English) Zbl 1432.68347 Ahn, Hee-Kap (ed.) et al., Algorithms and computation. 25th international symposium, ISAAC 2014, Jeonju, Korea, December 15–17, 2014. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 8889, 633-645 (2014). MSC: 68R10 05C62 05C85 68Q17 68Q25 68W25 PDFBibTeX XMLCite \textit{G. Da Lozzo} et al., Lect. Notes Comput. Sci. 8889, 633--645 (2014; Zbl 1432.68347) Full Text: DOI arXiv
Chaplick, Steven; Dorbec, Paul; Kratochvíl, Jan; Montassier, Mickael; Stacho, Juraj Contact representations of planar graphs: extending a partial representation is hard. (English) Zbl 1417.05133 Kratsch, Dieter (ed.) et al., Graph-theoretic concepts in computer science. 40th international workshop, WG 2014, Nouan-le-Fuzelier, France, June 25–27, 2014. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 8747, 139-151 (2014). MSC: 05C62 05C10 05C85 68Q25 68R10 PDFBibTeX XMLCite \textit{S. Chaplick} et al., Lect. Notes Comput. Sci. 8747, 139--151 (2014; Zbl 1417.05133) Full Text: DOI
Grilli, Luca; Hong, Seok-Hee; Kratochvíl, Jan; Rutter, Ignaz Drawing simultaneously embedded graphs with few bends. (English) Zbl 1426.68212 Duncan, Christian (ed.) et al., Graph drawing. 22nd international symposium, GD 2014, Würzburg, Germany, September 24–26, 2014. Revised selected papers. Berlin: Springer. Lect. Notes Comput. Sci. 8871, 40-51 (2014). MSC: 68R10 68Q25 68U05 PDFBibTeX XMLCite \textit{L. Grilli} et al., Lect. Notes Comput. Sci. 8871, 40--51 (2014; Zbl 1426.68212) Full Text: DOI
Gavenčiak, Tomáš; Kratochvíl, Jan; Prałat, Paweł Firefighting on square, hexagonal, and triangular grids. (English) Zbl 1301.05241 Discrete Math. 337, 142-155 (2014). MSC: 05C63 05C38 05C85 68R10 PDFBibTeX XMLCite \textit{T. Gavenčiak} et al., Discrete Math. 337, 142--155 (2014; Zbl 1301.05241) Full Text: DOI arXiv
Fiala, Jiří; Klavík, Pavel; Kratochvíl, Jan; Nedela, Roman Algorithmic aspects of regular graph covers with applications to planar graphs. (English) Zbl 1416.05224 Esparza, Javier (ed.) et al., Automata, languages, and programming. 41st international colloquium, ICALP 2014, Copenhagen, Denmark, July 8–11, 2014. Proceedings, Part I. Berlin: Springer. Lect. Notes Comput. Sci. 8572, 489-501 (2014). MSC: 05C70 05C10 05C85 68W40 68R10 PDFBibTeX XMLCite \textit{J. Fiala} et al., Lect. Notes Comput. Sci. 8572, 489--501 (2014; Zbl 1416.05224) Full Text: DOI arXiv
Jelínková, Eva; Kratochvíl, Jan On switching to \(H\)-free graphs. (English) Zbl 1292.05247 J. Graph Theory 75, No. 4, 387-405 (2014). MSC: 05C85 05C60 68R10 68Q25 PDFBibTeX XMLCite \textit{E. Jelínková} and \textit{J. Kratochvíl}, J. Graph Theory 75, No. 4, 387--405 (2014; Zbl 1292.05247) Full Text: DOI
Fiala, Jiří (ed.); Kratochvíl, Jan (ed.); Li, Angsheng (ed.) Preface. (English) Zbl 1280.00082 Theor. Comput. Sci. 494, 1 (2013). MSC: 00B25 68-06 68Q05 68Q10 PDFBibTeX XMLCite \textit{J. Fiala} (ed.) et al., Theor. Comput. Sci. 494, 1 (2013; Zbl 1280.00082) Full Text: DOI
Jelínek, Vít; Jelínková, Eva; Kratochvíl, Jan; Lidický, Bernard; Tesař, Marek; Vyskočil, Tomáš The planar slope number of planar partial 3-trees of bounded degree. (English) Zbl 1268.05052 Graphs Comb. 29, No. 4, 981-1005 (2013). MSC: 05C10 05C05 05C07 68R10 05C62 PDFBibTeX XMLCite \textit{V. Jelínek} et al., Graphs Comb. 29, No. 4, 981--1005 (2013; Zbl 1268.05052) Full Text: DOI arXiv
Kratochvíl, Jan (ed.); Miller, Mirka (ed.) Special issue: Combinatorial algorithms and complexity. Mainly selected papers based on the presentations at the 20th international workshop on combinatorial algorithms, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28 – July 2, 2009. (English) Zbl 1287.68008 Eur. J. Comb. 34, No. 3, 539-701 (2013). MSC: 68-06 68Rxx 68Wxx 00B25 PDFBibTeX XML
Kratochvíl, Jan (ed.); Miller, Mirka (ed.) Special issue on combinatorics and stringology. Selected papers based on the presentations at the 20th international workshop on combinatorial algorithms, IWOCA 2009, June 28 – July 2, 2009. (English) Zbl 1283.05007 Eur. J. Comb. 34, No. 1, 154 p. (2013). MSC: 05-06 05C05 68-06 68W05 00B25 PDFBibTeX XML
Abello, James; Klavík, Pavel; Kratochvíl, Jan; Vyskočil, Tomáš MSOL restricted contractibility to planar graphs. (English) Zbl 1374.68236 Thilikos, Dimitrios M. (ed.) et al., Parameterized and exact computation. 7th international symposium, IPEC 2012, Ljubljana, Slovenia, September 12–14, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-33292-0/pbk). Lecture Notes in Computer Science 7535, 194-205 (2012). MSC: 68Q25 05C10 05C85 68R10 PDFBibTeX XMLCite \textit{J. Abello} et al., Lect. Notes Comput. Sci. 7535, 194--205 (2012; Zbl 1374.68236) Full Text: DOI arXiv
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan; Lidický, Bernard; Paulusma, Daniël Distance three labelings of trees. (English) Zbl 1241.05123 Discrete Appl. Math. 160, No. 6, 764-779 (2012). MSC: 05C78 05C12 05C05 68M10 68R10 PDFBibTeX XMLCite \textit{J. Fiala} et al., Discrete Appl. Math. 160, No. 6, 764--779 (2012; Zbl 1241.05123) Full Text: DOI
Kratochvil, Jan Can they cross? and how? (the hitchhiker’s guide to the universe of geometric intersection graphs). (English) Zbl 1283.68371 Proceedings of the 27th annual symposium on computational geometry, SoCG 2011, Paris, France, June 13–15, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0682-9). 75-76 (2011). MSC: 68U05 05C62 68Q17 68R10 PDFBibTeX XMLCite \textit{J. Kratochvil}, in: Proceedings of the 27th annual symposium on computational geometry, SoCG 2011, Paris, France, June 13--15, 2011. New York, NY: Association for Computing Machinery (ACM). 75--76 (2011; Zbl 1283.68371) Full Text: DOI
Kolman, Petr (ed.); Kratochvíl, Jan (ed.) Graph-theoretic concepts in computer science. 37th international workshop, WG 2011, Teplá Monastery, Czech Republic, June 21–24, 2011. Revised papers. (English) Zbl 1228.68007 Lecture Notes in Computer Science 6986. Berlin: Springer (ISBN 978-3-642-25869-5/pbk). xi, 344 p. (2011). MSC: 68-06 68R10 00B25 PDFBibTeX XMLCite \textit{P. Kolman} (ed.) and \textit{J. Kratochvíl} (ed.), Graph-theoretic concepts in computer science. 37th international workshop, WG 2011, Teplá Monastery, Czech Republic, June 21--24, 2011. Revised papers. Berlin: Springer (2011; Zbl 1228.68007) Full Text: DOI
Horvat, Boris; Kratochvíl, Jan; Pisanski, Tomaž On the computational complexity of degenerate unit distance representations of graphs. (English) Zbl 1326.68160 Iliopoulos, Costas S. (ed.) et al., Combinatorial algorithms. 21st international workshop, IWOCA 2010, London, UK, July 26–28, 2010. Revised selected papers. Berlin: Springer (ISBN 978-3-642-19221-0/pbk). Lecture Notes in Computer Science 6460, 274-285 (2011). MSC: 68Q25 05C62 68Q17 68R10 PDFBibTeX XMLCite \textit{B. Horvat} et al., Lect. Notes Comput. Sci. 6460, 274--285 (2011; Zbl 1326.68160) Full Text: DOI arXiv
Havet, Frédéric; Klazar, Martin; Kratochvíl, Jan; Kratsch, Dieter; Liedloff, Mathieu Exact algorithms for \(L(2,1)\)-labeling of graphs. (English) Zbl 1213.68455 Algorithmica 59, No. 2, 169-194 (2011). MSC: 68R10 05C78 PDFBibTeX XMLCite \textit{F. Havet} et al., Algorithmica 59, No. 2, 169--194 (2011; Zbl 1213.68455) Full Text: DOI
Kratochvíl, Jan (ed.); Li, Angsheng (ed.); Fiala, Jiří (ed.); Kolman, Petr (ed.) Theory and applications of models of computation. 7th annual conference, TAMC 2010, Prague, Czech Republic, June 7–11, 2010. Proceedings. (English) Zbl 1189.68012 Lecture Notes in Computer Science 6108. Berlin: Springer (ISBN 978-3-642-13561-3/pbk). xiv, 480 p. (2010). MSC: 68-06 68Q05 00B25 PDFBibTeX XMLCite \textit{J. Kratochvíl} (ed.) et al., Theory and applications of models of computation. 7th annual conference, TAMC 2010, Prague, Czech Republic, June 7--11, 2010. Proceedings. Berlin: Springer (2010; Zbl 1189.68012) Full Text: DOI
Jelínek, Vít; Jelínková, Eva; Kratochvíl, Jan; Lidický, Bernard; Tesař, Marek; Vyskočil, Tomáš The planar slope number of planar partial 3-trees of bounded degree. (English) Zbl 1284.68465 Eppstein, David (ed.) et al., Graph drawing. 17th international symposium, GD 2009, Chicago, IL, USA, September 22–25, 2009. Revised papers. Berlin: Springer (ISBN 978-3-642-11804-3/pbk). Lecture Notes in Computer Science 5849, 304-315 (2010). MSC: 68R10 05C10 05C62 68U05 PDFBibTeX XMLCite \textit{V. Jelínek} et al., Lect. Notes Comput. Sci. 5849, 304--315 (2010; Zbl 1284.68465) Full Text: DOI
Coury, Michael D.; Hell, Pavol; Kratochvíl, Jan; Vyskočil, Tomáš Faithful representations of graphs by islands in the extended grid. (English) Zbl 1283.68269 López-Ortiz, Alejandro (ed.), LATIN 2010: Theoretical informatics. 9th Latin American symposium, Oaxaca, Mexico, April 19–23, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-12199-9/pbk). Lecture Notes in Computer Science 6034, 131-142 (2010). MSC: 68R10 PDFBibTeX XMLCite \textit{M. D. Coury} et al., Lect. Notes Comput. Sci. 6034, 131--142 (2010; Zbl 1283.68269) Full Text: DOI
Fiala, Jiří (ed.); Kratochvíl, Jan (ed.); Miller, Mirka (ed.) Combinatorial algorithms. 20th international workshop, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28–July 2, 2009. Revised selected papers. (English) Zbl 1177.68008 Lecture Notes in Computer Science 5874. Berlin: Springer (ISBN 978-3-642-10216-5/pbk). xii, 480 p. (2009). MSC: 68-06 68Rxx 68Wxx 00B25 PDFBibTeX XMLCite \textit{J. Fiala} (ed.) et al., Combinatorial algorithms. 20th international workshop, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28--July 2, 2009. Revised selected papers. Berlin: Springer (2009; Zbl 1177.68008) Full Text: DOI
Jelínek, Vít; Jelínková, Eva; Kratochvíl, Jan; Lidický, Bernard Clustered planarity: embedded clustered graphs with two-component clusters (extended abstract). (English) Zbl 1213.68459 Tollis, Ioannis G. (ed.) et al., Graph drawing. 16th international symposium, GD 2008, Heraklion, Crete, Greece, September 21–24, 2008. Revised papers. Berlin: Springer (ISBN 978-3-642-00218-2/pbk). Lecture Notes in Computer Science 5417, 121-132 (2009). MSC: 68R10 05C62 05C85 PDFBibTeX XMLCite \textit{V. Jelínek} et al., Lect. Notes Comput. Sci. 5417, 121--132 (2009; Zbl 1213.68459) Full Text: DOI
Fiala, Jiří; Kratochvíl, Jan Locally constrained graph homomorphisms – structure, complexity, and applications. (English) Zbl 1302.05122 Comput. Sci. Rev. 2, No. 2, 97-111 (2008). MSC: 05C60 05C15 05C70 05C85 68R10 05-02 PDFBibTeX XMLCite \textit{J. Fiala} and \textit{J. Kratochvíl}, Comput. Sci. Rev. 2, No. 2, 97--111 (2008; Zbl 1302.05122) Full Text: DOI Backlinks: MO
Jelínková, Eva; Kratochvíl, Jan On switching to \(H\)-free graphs. (English) Zbl 1175.68298 Ehrig, Hartmut (ed.) et al., Graph transformations. 4th international conference, ICGT 2008, Leicester, United Kingdom, September 7–13, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-87404-1/pbk). Lecture Notes in Computer Science 5214, 379-395 (2008). MSC: 68R10 05C85 68Q42 PDFBibTeX XMLCite \textit{E. Jelínková} and \textit{J. Kratochvíl}, Lect. Notes Comput. Sci. 5214, 379--395 (2008; Zbl 1175.68298) Full Text: DOI
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan Computational complexity of the distance constrained labeling problem for trees (extended abstract). (English) Zbl 1153.68390 Aceto, Luca (ed.) et al., Automata, languages and programming. 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008. Proceedings, Part I. Berlin: Springer (ISBN 978-3-540-70574-1/pbk). Lecture Notes in Computer Science 5125, 294-305 (2008). MSC: 68Q25 68Q17 68R10 05C78 PDFBibTeX XMLCite \textit{J. Fiala} et al., Lect. Notes Comput. Sci. 5125, 294--305 (2008; Zbl 1153.68390) Full Text: DOI
Golovach, Petr; Kratochvíl, Jan Generalized domination in degenerate graphs: A complete dichotomy of computational complexity. (English) Zbl 1139.68344 Agrawal, Manindra (ed.) et al., Theory and applications of models of computation. 5th international conference, TAMC 2008, Xi’an, China, April 25–29, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79227-7/pbk). Lecture Notes in Computer Science 4978, 182-191 (2008). MSC: 68Q25 05C69 05C85 68Q17 68R10 PDFBibTeX XMLCite \textit{P. Golovach} and \textit{J. Kratochvíl}, Lect. Notes Comput. Sci. 4978, 182--191 (2008; Zbl 1139.68344) Full Text: DOI
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan Distance constrained labelings of trees. (English) Zbl 1139.05341 Agrawal, Manindra (ed.) et al., Theory and applications of models of computation. 5th international conference, TAMC 2008, Xi’an, China, April 25–29, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79227-7/pbk). Lecture Notes in Computer Science 4978, 125-135 (2008). MSC: 05C78 05C05 05C85 68Q17 68Q25 68R10 PDFBibTeX XMLCite \textit{J. Fiala} et al., Lect. Notes Comput. Sci. 4978, 125--135 (2008; Zbl 1139.05341) Full Text: DOI
Fomin, Fedor V.; Kratochvíl, Jan; Lokshtanov, Daniel; Mancini, Federico; Telle, Jan Arne On the complexity of reconstructing \(H\)-free graphs from their star systems. (English) Zbl 1136.68459 Laber, Eduardo Sany (ed.) et al., LATIN 2008: Theoretical informatics. 8th Latin American symposium, Búzios, Brazil, April 7–11, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-78772-3/pbk). Lecture Notes in Computer Science 4957, 194-205 (2008). MSC: 68R10 68Q25 PDFBibTeX XMLCite \textit{F. V. Fomin} et al., Lect. Notes Comput. Sci. 4957, 194--205 (2008; Zbl 1136.68459) Full Text: DOI
Jelínková, Eva; Kára, Jan; Kratochvíl, Jan; Pergel, Martin; Suchý, Ondřej; Vyskočil, Tomáš Clustered planarity: Small clusters in Eulerian graphs. (English) Zbl 1137.68495 Hong, Seok-Hee (ed.) et al., Graph drawing. 15th international symposium, GD 2007, Sydney, Australia, September 24–26, 2007. Revised papers. Berlin: Springer (ISBN 978-3-540-77536-2/pbk). Lecture Notes in Computer Science 4875, 303-314 (2008). MSC: 68R10 68U05 05C45 05C62 05C85 PDFBibTeX XMLCite \textit{E. Jelínková} et al., Lect. Notes Comput. Sci. 4875, 303--314 (2008; Zbl 1137.68495) Full Text: DOI
Goaoc, Xavier; Kratochvíl, Jan; Okamoto, Yoshio; Shin, Chan-Su; Wolff, Alexander Moving vertices to make drawings plane. (English) Zbl 1137.68490 Hong, Seok-Hee (ed.) et al., Graph drawing. 15th international symposium, GD 2007, Sydney, Australia, September 24–26, 2007. Revised papers. Berlin: Springer (ISBN 978-3-540-77536-2/pbk). Lecture Notes in Computer Science 4875, 101-112 (2008). MSC: 68R10 68U05 05C62 68Q25 PDFBibTeX XMLCite \textit{X. Goaoc} et al., Lect. Notes Comput. Sci. 4875, 101--112 (2008; Zbl 1137.68490) Full Text: DOI
Kratochvíl, Jan; Pergel, Martin Geometric intersection graphs: do short cycles help? (Extended abstract). (English) Zbl 1206.05069 Lin, Guohui (ed.), Computing and combinatorics. 13th annual international conference, COCOON 2007, Banff, Canada, July 16–19, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73544-1/pbk). Lecture Notes in Computer Science 4598, 118-128 (2007). MSC: 05C62 05C38 05C85 68Q25 68R10 PDFBibTeX XMLCite \textit{J. Kratochvíl} and \textit{M. Pergel}, Lect. Notes Comput. Sci. 4598, 118--128 (2007; Zbl 1206.05069) Full Text: DOI
Golovach, Petr; Kratochvíl, Jan Computational complexity of generalized domination: A complete dichotomy for chordal graphs. (English) Zbl 1141.68530 Brandstädt, Andreas (ed.) et al., Graph-theoretic concepts in computer science. 33rd international workshop, WG 2007, Dornburg, Germany, June 21–23, 2007. Revised papers. Berlin: Springer (ISBN 978-3-540-74838-0/pbk). Lecture Notes in Computer Science 4769, 1-11 (2007). MSC: 68R10 05C69 05C85 68Q25 PDFBibTeX XMLCite \textit{P. Golovach} and \textit{J. Kratochvíl}, Lect. Notes Comput. Sci. 4769, 1--11 (2007; Zbl 1141.68530) Full Text: DOI
Kratochvíl, Jan (ed.); Díaz, Josep (ed.); Fiala, Jiří (ed.) Special issue: 29th symposium on mathematical foundations of computer science MFCS 2004. Selected papers based on the presentations at the symposium, Prague, Czech Republic, August 22–27, 2004. (English) Zbl 1109.68316 Discrete Appl. Math. 155, No. 2, 79-256 p. (2007). MSC: 68-06 05-06 00B25 PDFBibTeX XML
Kaufmann, Michael; Kratochvíl, Jan; Lehmann, Katharina A.; Subramanian, Amarendran R. Max-tolerance graphs as intersection graphs: cliques, cycles and recognition. (English) Zbl 1192.05102 Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, January 22–24, 2006. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-605-5). 832-841 (2006). MSC: 05C62 68R10 PDFBibTeX XMLCite \textit{M. Kaufmann} et al., in: Proceedings of the seventeenth annual ACM-SIAM symposium on discrete algorithms, SODA 2006, Miami, FL, January 22--24, 2006. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 832--841 (2006; Zbl 1192.05102) Full Text: DOI
Fiala, Jiří; Kratochvíl, Jan Locally injective graph homomorphism: Lists guarantee dichotomy. (English) Zbl 1167.68406 Fomin, Fedor V. (ed.), Graph-theoretic concepts in computer science. 32nd international workshop, WG 2006, Bergen, Norway, June 22–24, 2006. Revised papers. Berlin: Springer (ISBN 978-3-540-48381-6/pbk). Lecture Notes in Computer Science 4271, 15-26 (2006). MSC: 68R10 05C15 68Q25 PDFBibTeX XMLCite \textit{J. Fiala} and \textit{J. Kratochvíl}, Lect. Notes Comput. Sci. 4271, 15--26 (2006; Zbl 1167.68406) Full Text: DOI
Broersma, Hajo; Fomin, Fedor V.; Kratochvil, Jan; Woeginger, Gerhard J. Planar graph coloring avoiding monochromatic subgraphs: Trees and paths make it difficult. (English) Zbl 1095.68075 Algorithmica 44, No. 4, 343-361 (2006). MSC: 68R10 68Q25 05C15 05C70 PDFBibTeX XMLCite \textit{H. Broersma} et al., Algorithmica 44, No. 4, 343--361 (2006; Zbl 1095.68075) Full Text: DOI Link
Král, Daniel; Kratochvíl, Jan; Proskurowski, Andrzej; Voss, Heinz-Jürgen Coloring mixed hypertrees. (English) Zbl 1088.05031 Discrete Appl. Math. 154, No. 4, 660-672 (2006). Reviewer: Van Bang Le (Rostock) MSC: 05C15 05C65 68R10 PDFBibTeX XMLCite \textit{D. Král} et al., Discrete Appl. Math. 154, No. 4, 660--672 (2006; Zbl 1088.05031) Full Text: DOI
Fiala, Jiří; Kratochvíl, Jan On the computational complexity of the \(L_{(2,1)}\)-labeling problem for regular graphs. (English) Zbl 1171.68612 Coppo, Mario (ed.) et al., Theoretical computer science. 9th Italian conference, ICTCS 2005, Siena, Italy, October 12–14, 2005. Proceedings. Berlin: Springer (ISBN 3-540-29106-7/pbk). Lecture Notes in Computer Science 3701, 228-236 (2005). MSC: 68R10 05C78 68Q17 68Q25 PDFBibTeX XMLCite \textit{J. Fiala} and \textit{J. Kratochvíl}, Lect. Notes Comput. Sci. 3701, 228--236 (2005; Zbl 1171.68612) Full Text: DOI
Koubek, Václav (ed.); Kratochvíl, Jan (ed.) Mathematical foundations of computer science 2004. Selected papers based on the presentations at the 29th symposium on mathematical foundations of computer science (MFCS’04), Prague, Czech Republic, August 22–27, 2004. (English) Zbl 1093.68514 Theor. Comput. Sci. 345, No. 2-3, 171-506 (2005). MSC: 68-06 00B15 PDFBibTeX XML
Kára, Jan; Kratochvíl, Jan; Wood, David R. On the complexity of the balanced vertex ordering problem. (English) Zbl 1128.68402 Wang, Lusheng (ed.), Computing and combinatorics. 11th annual international conference, COCOON 2005, Kunming, China, August 16–29, 2005. Proceedings. Berlin: Springer (ISBN 3-540-28061-8/pbk). Lecture Notes in Computer Science 3595, 849-858 (2005). MSC: 68R10 05C85 68Q25 PDFBibTeX XMLCite \textit{J. Kára} et al., Lect. Notes Comput. Sci. 3595, 849--858 (2005; Zbl 1128.68402) Full Text: DOI
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan Distance constrained labelings of graphs of bounded treewidth. (English) Zbl 1082.68080 Caires, Luís (ed.) et al., Automata, languages and programming. 32nd international colloquium, ICALP 2005, Lisbon, Portugal, July 11–15, 2005. Proceedings. Berlin: Springer (ISBN 3-540-27580-0/pbk). Lecture Notes in Computer Science 3580, 360-372 (2005). MSC: 68R10 68Q25 05C78 PDFBibTeX XMLCite \textit{J. Fiala} et al., Lect. Notes Comput. Sci. 3580, 360--372 (2005; Zbl 1082.68080) Full Text: DOI
Fiala, Jiří; Kratochvíl, Jan; Proskurowski, Andrzej Systems of distant representatives. (English) Zbl 1084.05059 Discrete Appl. Math. 145, No. 2, 306-316 (2005). MSC: 05C78 54E35 68R10 PDFBibTeX XMLCite \textit{J. Fiala} et al., Discrete Appl. Math. 145, No. 2, 306--316 (2005; Zbl 1084.05059) Full Text: DOI
Kloks, Ton; Kratochvíl, Jan; Müller, Haiko Computing the branchwidth of interval graphs. (English) Zbl 1084.05068 Discrete Appl. Math. 145, No. 2, 266-275 (2005). MSC: 05C85 68R10 68W05 PDFBibTeX XMLCite \textit{T. Kloks} et al., Discrete Appl. Math. 145, No. 2, 266--275 (2005; Zbl 1084.05068) Full Text: DOI
Kratochvíl, Jan; Pergel, Martin Two results on intersection graphs of polygons. (English) Zbl 1215.05117 Liotta, Giuseppe (ed.), Graph drawing. 11th international symposium, GD 2003, Perugia, Italy, September 21–24, 2003. Revised papers. Berlin: Springer (ISBN 3-540-20831-3/pbk). Lect. Notes Comput. Sci. 2912, 59-70 (2004). MSC: 05C62 52B05 68Q17 68R10 PDFBibTeX XMLCite \textit{J. Kratochvíl} and \textit{M. Pergel}, Lect. Notes Comput. Sci. 2912, 59--70 (2004; Zbl 1215.05117) Full Text: DOI
Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan Elegant distance constrained labelings of trees. (English) Zbl 1112.68419 Hromkovič, Juraj (ed.) et al., Graph-theoretic concepts in computer science. 30th international workshop, WG 2004, Bad Honnef, Germany, June 21–23, 2004. Revised papers. Berlin: Springer (ISBN 3-540-24132-9/pbk). Lecture Notes in Computer Science 3353, 58-67 (2004). MSC: 68R10 05C78 PDFBibTeX XMLCite \textit{J. Fiala} et al., Lect. Notes Comput. Sci. 3353, 58--67 (2004; Zbl 1112.68419) Full Text: DOI
Fiala, Jiří (ed.); Koubek, Václav (ed.); Kratochvíl, Jan (ed.) Mathematical foundations of computer science 2004. 29th international symposium, MFCS 2004, Prague, Czech Republic, August 22–27, 2004. Proceedings. (English) Zbl 1058.68005 Lecture Notes in Computer Science 3153. Berlin: Springer (ISBN 3-540-22823-3/pbk). xiv, 902 p. (2004). MSC: 68-06 68Qxx 00B25 PDFBibTeX XMLCite \textit{J. Fiala} (ed.) et al., Mathematical foundations of computer science 2004. 29th international symposium, MFCS 2004, Prague, Czech Republic, August 22--27, 2004. Proceedings. Berlin: Springer (2004; Zbl 1058.68005) Full Text: DOI
Král’, Daniel; Kratochvíl, Jan; Voss, Heinz-Jürgen Mixed hypergraphs with bounded degree: Edge-coloring of mixed multigraphs. (English) Zbl 1051.68114 Theor. Comput. Sci. 295, No. 1-3, 263-278 (2003). MSC: 68R10 05C15 05C65 05C85 PDFBibTeX XMLCite \textit{D. Král'} et al., Theor. Comput. Sci. 295, No. 1--3, 263--278 (2003; Zbl 1051.68114) Full Text: DOI
Broersma, Hajo; Fomin, Fedor V.; Kratochvíl, Jan; Woeginger, Gerhard J. Planar graph coloring with forbidden subgraphs: Why trees and paths are dangerous. (English) Zbl 1078.68673 Penttonen, Martti (ed.) et al., Algorithm theory - SWAT 2002. 8th Scandinavian workshop, Turku, Finland, July 3–5, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43866-1). Lect. Notes Comput. Sci. 2368, 160-169 (2002). MSC: 68R10 05C10 05C15 68Q25 PDFBibTeX XMLCite \textit{H. Broersma} et al., Lect. Notes Comput. Sci. 2368, 160--169 (2002; Zbl 1078.68673) Full Text: Link
Fiala, Jirí; Kratochvíl, Jan; Proskurowski, Andrzej Geometric systems of disjoint representatives. (English) Zbl 1037.68584 Goodrich, Michael T. (ed.) et al., Graph drawing. 10th international symposium, GD 2002, Irvine, CA, USA, August 26–28, 2002. Revised papers. Berlin: Springer (ISBN 3-540-00158-1/pbk). Lect. Notes Comput. Sci. 2528, 110-117 (2002). MSC: 68R10 68U05 05C85 PDFBibTeX XMLCite \textit{J. Fiala} et al., Lect. Notes Comput. Sci. 2528, 110--117 (2002; Zbl 1037.68584) Full Text: Link
Kratochvíl, Jan; Tuza, Zsolt On the complexity of bicoloring clique hypergraphs of graphs. (English) Zbl 1030.68066 J. Algorithms 45, No. 1, 40-54 (2002). MSC: 68R10 PDFBibTeX XMLCite \textit{J. Kratochvíl} and \textit{Z. Tuza}, J. Algorithms 45, No. 1, 40--54 (2002; Zbl 1030.68066) Full Text: DOI
Fiala, Jiří; Kratochvíl, Jan Partial covers of graphs. (English) Zbl 1017.05094 Discuss. Math., Graph Theory 22, No. 1, 89-99 (2002). Reviewer: Hans L.Bodlaender (Utrecht) MSC: 05C85 05C78 68R10 05C15 PDFBibTeX XMLCite \textit{J. Fiala} and \textit{J. Kratochvíl}, Discuss. Math., Graph Theory 22, No. 1, 89--99 (2002; Zbl 1017.05094) Full Text: DOI
de Fraysseix, Hubert (ed.); Kratochvíl, Jan (ed.) Graph drawing and representations. Special issue on selected papers from the 7th international symposium on graph drawing, GD’99, Stirín Castle, Prague, Czech Republic, September 15–19, 1999. (English) Zbl 0990.00041 J. Graph Algorithms Appl. 6, No. 1, 153 p. (2002). MSC: 00B25 05-06 68-06 PDFBibTeX XMLCite \textit{H. de Fraysseix} (ed.) and \textit{J. Kratochvíl} (ed.), J. Graph Algorithms Appl. 6, No. 1, 153~p. (2002; Zbl 0990.00041) Full Text: DOI
Fiala, Jirí; Kratochvíl, Jan Complexity of partial covers of graphs. (English) Zbl 1077.68725 Eades, Peter (ed.) et al., Algorithms and computation. 12th international symposium, ISAAC 2001, Christchurch, New Zealand, December 19–21, 2001. Proceedings. Berlin: Springer (ISBN 3-540-42985-9). Lect. Notes Comput. Sci. 2223, 537-549 (2001). MSC: 68R10 05C70 05C85 68Q25 PDFBibTeX XMLCite \textit{J. Fiala} and \textit{J. Kratochvíl}, Lect. Notes Comput. Sci. 2223, 537--549 (2001; Zbl 1077.68725) Full Text: Link
Král’, Daniel; Kratochvíl, Jan; Tuza, Zsolt; Woeginger, Gerhard J. Complexity of coloring graphs without forbidden induced subgraphs. (English) Zbl 1042.68639 Brandstädt, Andreas (ed.) et al., Graph-theoretic concepts in computer science. 27th international workshop, WG 2001, Boltenhagen, Germany, June 14–16, 2001. Proceedings. Berlin: Springer (ISBN 3-540-42707-4). Lect. Notes Comput. Sci. 2204, 254-262 (2001). MSC: 68R10 05C15 68Q25 PDFBibTeX XMLCite \textit{D. Král'} et al., Lect. Notes Comput. Sci. 2204, 254--262 (2001; Zbl 1042.68639) Full Text: Link
Fiala, Jiří; Kloks, Ton; Kratochvíl, Jan Fixed-parameter complexity of \(\lambda\)-labelings. (English) Zbl 0982.05085 Discrete Appl. Math. 113, No. 1, 59-72 (2001). Reviewer: Hans L.Bodlaender (Utrecht) MSC: 05C78 68R10 05C90 05C15 PDFBibTeX XMLCite \textit{J. Fiala} et al., Discrete Appl. Math. 113, No. 1, 59--72 (2001; Zbl 0982.05085) Full Text: DOI
Babel, Luitpold; Kloks, Ton; Kratochvil, Jan; Kratsch, Dieter; Müller, Haiko; Olariu, Stephan Efficient algorithms for graphs with few \(P_4\)’s. (English) Zbl 0980.05045 Discrete Math. 235, No. 1-3, 29-51 (2001). Reviewer: Zhi-Hong Chen (Indianapolis) MSC: 05C85 05C70 05C69 05C15 68R10 PDFBibTeX XMLCite \textit{L. Babel} et al., Discrete Math. 235, No. 1--3, 29--51 (2001; Zbl 0980.05045) Full Text: DOI
Hliněný, Petr; Kratochvíl, Jan Representing graphs by disks and balls (a survey of recognition-complexity results). (English) Zbl 0969.68118 Discrete Math. 229, No. 1-3, 101-124 (2001). MSC: 68R10 05C62 PDFBibTeX XMLCite \textit{P. Hliněný} and \textit{J. Kratochvíl}, Discrete Math. 229, No. 1--3, 101--124 (2001; Zbl 0969.68118) Full Text: DOI
Fiedler, M. (ed.); Kratochvíl, J. (ed.); Nešetřil, J. (ed.) Combinatorics, graph theory, algorithms and applications. (English) Zbl 0969.00073 Discrete Math. 229, No. 1-3, 412 p. (2001). MSC: 00B25 05-06 68-06 PDFBibTeX XMLCite \textit{M. Fiedler} (ed.) et al., Discrete Math. 229, No. 1--3, 412 p. (2001; Zbl 0969.00073) Full Text: DOI
Kratochvil, Jan (ed.) Graph drawing. 7th international symposium, GD ’99, Štiřín Castle, Czech Republic, September 15–19, 1999. Proceedings. (English) Zbl 0931.00046 Lecture Notes in Computer Science. 1731. Berlin: Springer. xiii, 422 p. (1999). MSC: 00B25 68-06 05-06 PDFBibTeX XMLCite \textit{J. Kratochvil} (ed.), Graph drawing. 7th international symposium, GD '99, Štiřín Castle, Czech Republic, September 15--19, 1999. Proceedings. Berlin: Springer (1999; Zbl 0931.00046) Full Text: DOI
Graham, Ronald L. (ed.); Kratochvíl (ed.); Nešetřil, Jaroslav (ed.); Roberts, Fred S. (ed.) Contemporary trends in discrete mathematics. From DIMACS and DIMATIA to the future. Proceedings of the DIMATIA-DIMACS conference, Štiřín Castle, Czech Republic, May 19–25, 1997. (English) Zbl 0919.00042 DIMACS. Series in Discrete Mathematics and Theoretical Computer Science. 49. Providence, RI: American Mathematical Society (AMS). xviii, 389 p. (1999). MSC: 00B25 05-06 68-06 PDFBibTeX XMLCite \textit{R. L. Graham} (ed.) et al., Contemporary trends in discrete mathematics. From DIMACS and DIMATIA to the future. Proceedings of the DIMATIA-DIMACS conference, Štiřín Castle, Czech Republic, May 19--25, 1997. Providence, RI: American Mathematical Society (1999; Zbl 0919.00042)
Kratochvíl, Jan; Tuza, Zsolt Rankings of directed graphs. (Extended abstract). (English) Zbl 0918.68084 Hromkovič, Juraj (ed.) et al., Graph-theoretic concepts in computer science. 24th international workshop, WG ’98, Smolenice Castle, Slovak Republic, June 18–20, 1998. Proceecdings. Berlin: Springer. Lect. Notes Comput. Sci. 1517, 114-123 (1998). MSC: 68R10 05C15 05C05 05C20 05C85 PDFBibTeX XMLCite \textit{J. Kratochvíl} and \textit{Z. Tuza}, Lect. Notes Comput. Sci. 1517, 114--123 (1998; Zbl 0918.68084)
Kratochvíl, Jan; Proskurowski, Andrzej; Telle, Jan Arne Complexity of graph covering problems. (English) Zbl 0911.68076 Nord. J. Comput. 5, No. 3, 173-195 (1998). MSC: 68W10 68R10 PDFBibTeX XMLCite \textit{J. Kratochvíl} et al., Nord. J. Comput. 5, No. 3, 173--195 (1998; Zbl 0911.68076)
Kratochvíl, Jan; Kuběna, Aleš On intersection representations of co-planar graphs. (English) Zbl 0897.05030 Discrete Math. 178, No. 1-3, 251-255 (1998). Reviewer: M.Middendorf (Karlsruhe) MSC: 05C10 68R10 PDFBibTeX XMLCite \textit{J. Kratochvíl} and \textit{A. Kuběna}, Discrete Math. 178, No. 1--3, 251--255 (1998; Zbl 0897.05030) Full Text: DOI
Kratochvíl, Jan; Schiermeyer, Ingo On the computational complexity of \(({\mathcal O},{\mathcal P})\)-partition problems. (English) Zbl 0904.05074 Discuss. Math., Graph Theory 17, No. 2, 253-258 (1997). Reviewer: S.L.Bezrukov (Paderborn) MSC: 05C75 68Q15 68R10 PDFBibTeX XMLCite \textit{J. Kratochvíl} and \textit{I. Schiermeyer}, Discuss. Math., Graph Theory 17, No. 2, 253--258 (1997; Zbl 0904.05074) Full Text: DOI
Kratochvíl, Jan; Proskurowski, Andrzej; Telle, Jan Arne Covering regular graphs. (English) Zbl 0895.05049 J. Comb. Theory, Ser. B 71, No. 1, 1-16 (1997). Reviewer: K.Dohmen (Berlin) MSC: 05C70 68R10 PDFBibTeX XMLCite \textit{J. Kratochvíl} et al., J. Comb. Theory, Ser. B 71, No. 1, 1--16 (1997; Zbl 0895.05049) Full Text: DOI Link
Kratochvíl, Jan; Proskurowski, Andrzej; Telle, Jan Arne Complexity of colored graph covers. I: Colored directed multigraphs. (English) Zbl 0890.68095 Möhring, Rolf H. (ed.), Graph-theoretic concepts in computer science. 23rd international workshop, WG ’97, Berlin, Germany, June 18–20, 1997. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1335, 242-257 (1997). MSC: 68R10 05C15 05C70 PDFBibTeX XMLCite \textit{J. Kratochvíl} et al., Lect. Notes Comput. Sci. 1335, 242--257 (1997; Zbl 0890.68095)
Hliněný, Petr; Kratochvíl, Jan Compuational complexity of the Krausz dimension of graphs. (English) Zbl 0890.68094 Möhring, Rolf H. (ed.), Graph-theoretic concepts in computer science. 23rd international workshop, WG ’97, Berlin, Germany, June 18–20, 1997. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1335, 214-228 (1997). MSC: 68R10 05C35 05C70 PDFBibTeX XMLCite \textit{P. Hliněný} and \textit{J. Kratochvíl}, Lect. Notes Comput. Sci. 1335, 214--228 (1997; Zbl 0890.68094)
Dahlhaus, Elias; Kratochvil, Jan; Manuel, Paul D.; Miller, Mirka Transversal partitioning in balanced hypergraphs. (English) Zbl 0887.05039 Discrete Appl. Math. 79, No. 1-3, 75-89 (1997). Reviewer: M.Middendorf (Karlsruhe) MSC: 05C65 05C70 68R10 PDFBibTeX XMLCite \textit{E. Dahlhaus} et al., Discrete Appl. Math. 79, No. 1--3, 75--89 (1997; Zbl 0887.05039) Full Text: DOI Link
Kratochvíl, Jan; Manuel, Paul D.; Miller, Mirka Generalized domination in chordal graphs. (English) Zbl 0849.68037 Nord. J. Comput. 2, No. 1, 41-50 (1995). MSC: 68Q15 68R10 PDFBibTeX XMLCite \textit{J. Kratochvíl} et al., Nord. J. Comput. 2, No. 1, 41--50 (1995; Zbl 0849.68037)
Kratochvíl, Jan; Proskurowski, Andrzej; Telle, Jan Arne Complexity of graph covering problems. (English) Zbl 1528.68306 Mayr, Ernst W. (ed.) et al., Graph-theoretic concepts in computer science. 20th international workshop. WG ’94, Herrsching, Germany, June 16–18, 1994. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 903, 93-105 (1995). MSC: 68R10 05C70 05C85 68Q25 PDFBibTeX XMLCite \textit{J. Kratochvíl} et al., Lect. Notes Comput. Sci. 903, 93--105 (1995; Zbl 1528.68306) Full Text: DOI
Fellows, M. R.; Kratochvíl, J.; Middendorf, M.; Pfeiffer, F. The complexity of induced minors and related problems. (English) Zbl 0816.68070 Algorithmica 13, No. 3, 266-282 (1995). MSC: 68Q15 68R10 PDFBibTeX XMLCite \textit{M. R. Fellows} et al., Algorithmica 13, No. 3, 266--282 (1995; Zbl 0816.68070) Full Text: DOI
Kratochvíl, Jan; Matoušek, Jiří Intersection graphs of segments. (English) Zbl 0808.68075 J. Comb. Theory, Ser. B 62, No. 2, 289-315 (1994). Reviewer: J.Kratochvíl and J.Matoušek (Praha) MSC: 68R10 68U05 51M30 03D15 68Q25 PDFBibTeX XMLCite \textit{J. Kratochvíl} and \textit{J. Matoušek}, J. Comb. Theory, Ser. B 62, No. 2, 289--315 (1994; Zbl 0808.68075) Full Text: DOI
Kratochvíl, Jan Regular codes in regular graphs are difficult. (English) Zbl 0821.68096 Discrete Math. 133, No. 1-3, 191-205 (1994). MSC: 68R10 68Q25 PDFBibTeX XMLCite \textit{J. Kratochvíl}, Discrete Math. 133, No. 1--3, 191--205 (1994; Zbl 0821.68096) Full Text: DOI
Kratochvíl, Jan A special planar satisfiability problem and a consequence of its NP- completeness. (English) Zbl 0810.68083 Discrete Appl. Math. 52, No. 3, 233-252 (1994). MSC: 68Q25 68R10 PDFBibTeX XMLCite \textit{J. Kratochvíl}, Discrete Appl. Math. 52, No. 3, 233--252 (1994; Zbl 0810.68083) Full Text: DOI
Kratochvíl, J. Precoloring extension with fixed color bound. (English) Zbl 0821.05027 Acta Math. Univ. Comen., New Ser. 62, No. 2, 139-153 (1993). MSC: 05C15 05C85 68Q15 68R10 PDFBibTeX XMLCite \textit{J. Kratochvíl}, Acta Math. Univ. Comen., New Ser. 62, No. 2, 139--153 (1993; Zbl 0821.05027) Full Text: EuDML EMIS
Fellows, Michael; Kratochvíl, Jan; Middendorf, Matthias; Pfeiffer, Frank Induced minors and related problems. (English) Zbl 0796.68118 Robertson, Neil (ed.) et al., Graph structure theory. Proceedings of the AMS-IMS-SIAM joint summer research conference on graph minors held June 22 to July 5, 1991 at the University of Washington, Seattle, WA (USA). Providence, RI: American Mathematical Society. Contemp. Math. 147, 179-182 (1993). Reviewer: C.McDiarmid (Oxford) MSC: 68Q25 05C20 68R10 05C55 05C85 05C10 PDFBibTeX XMLCite \textit{M. Fellows} et al., Contemp. Math. 147, 179--182 (1993; Zbl 0796.68118)
Kratochvíl, Jan; Nešetřil, Jaroslav; Zýka, Ondřej On the computational complexity of Seidel’s switching. (English) Zbl 0768.68047 Combinatorics, graphs and complexity, Proc. 4th Czech. Symp., Prachatice/Czech. 1990, Ann. Discrete Math. 51, 161-166 (1992). MSC: 68Q25 68R10 05C60 PDFBibTeX XMLCite \textit{J. Kratochvíl} et al., Ann. Discrete Math. 51, 161--166 (1992; Zbl 0768.68047)
Kratochvíl, Jan String graphs. II: Recognizing string graphs is NP-hard. (English) Zbl 0661.05054 J. Comb. Theory, Ser. B 52, No. 1, 67-78 (1991). Reviewer: Jan Kratochvíl MSC: 05C75 68R10 PDFBibTeX XMLCite \textit{J. Kratochvíl}, J. Comb. Theory, Ser. B 52, No. 1, 67--78 (1991; Zbl 0661.05054) Full Text: DOI