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
Klavík, Pavel; Kratochvíl, Jan; Otachi, Yota; Rutter, Ignaz; Saitoh, Toshiki; Saumell, Maria; Vyskočil, Tomáš Extending partial representations of proper and unit interval graphs. (English) Zbl 1360.05167 Algorithmica 77, No. 4, 1071-1104 (2017). MSC: 05C85 05C62 68Q17 PDFBibTeX XMLCite \textit{P. Klavík} et al., Algorithmica 77, No. 4, 1071--1104 (2017; Zbl 1360.05167) Full Text: DOI arXiv
Klavík, Pavel; Kratochvíl, Jan; Otachi, Yota; Saitoh, Toshiki Extending partial representations of subclasses of chordal graphs. (English) Zbl 1311.05133 Theor. Comput. Sci. 576, 85-101 (2015). MSC: 05C62 PDFBibTeX XMLCite \textit{P. Klavík} et al., Theor. Comput. Sci. 576, 85--101 (2015; Zbl 1311.05133) Full Text: DOI
Klavík, Pavel; Kratochvíl, Jan; Vyskočil, Tomáš Extending partial representations of interval graphs. (English) Zbl 1331.68107 Ogihara, Mitsunori (ed.) et al., Theory and applications of models of computation. 8th annual conference, TAMC 2011, Tokyo, Japan, May 23–25, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-20876-8/pbk). Lecture Notes in Computer Science 6648, 276-285 (2011). MSC: 68Q25 05C62 05C85 PDFBibTeX XMLCite \textit{P. Klavík} et al., Lect. Notes Comput. Sci. 6648, 276--285 (2011; Zbl 1331.68107) 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
Dourado, Mitre C.; Gimbel, John G.; Kratochvíl, Jan; Protti, Fábio; Szwarcfiter, Jayme L. On the computation of the hull number of a graph. (English) Zbl 1215.05184 Discrete Math. 309, No. 18, 5668-5674 (2009). MSC: 05C85 PDFBibTeX XMLCite \textit{M. C. Dourado} et al., Discrete Math. 309, No. 18, 5668--5674 (2009; Zbl 1215.05184) 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
Fiala, Jiří; Kratochvíl, Jan; Pór, Attila On the computational complexity of partial covers of theta graphs. (English) Zbl 1138.05061 Discrete Appl. Math. 156, No. 7, 1143-1149 (2008). MSC: 05C75 PDFBibTeX XMLCite \textit{J. Fiala} et al., Discrete Appl. Math. 156, No. 7, 1143--1149 (2008; Zbl 1138.05061) 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
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; 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 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
Kratochvíl, Jan; Poljak, Svatopluk Compatible 2-factors. (English) Zbl 0778.05064 Discrete Appl. Math. 36, No. 3, 253-266 (1992). Reviewer: P.Hell (Burnaby) MSC: 05C70 68Q25 PDFBibTeX XMLCite \textit{J. Kratochvíl} and \textit{S. Poljak}, Discrete Appl. Math. 36, No. 3, 253--266 (1992; Zbl 0778.05064) Full Text: DOI