6 citations · 15 across the 8 of their papers we have counts for
8 papers
On the Structure of Hamiltonian Graphs with Small Independence Number
Nikola Jedličková, Jan Kratochvíl
A Hamiltonian path (cycle) in a graph is a path (cycle, respectively) which passes through all of its vertices. The problems of deciding the existence of a Hamiltonian cycle (path)…
On a Combinatorial Problem Arising in Machine Teaching
Brigt Håvardstun, Jan Kratochvíl, Joakim Sunde +1
We study a model of machine teaching where the teacher mapping is constructed from a size function on both concepts and examples. The main question in machine teaching is the minim…
Computational Complexity of Covering Disconnected Multigraphs
Jan Bok, Jiří Fiala, Nikola Jedličková +2
The notion of graph covers is a discretization of covering spaces introduced and deeply studied in topology. In discrete mathematics and theoretical computer science, they have att…
Algorithmic Aspects of Regular Graph Covers
Jiří Fiala, Pavel Klavík, Jan Kratochvíl +1
A graph covers a graph if there exists a locally bijective homomorphism from to . We deal with regular covers where this homomorphism is prescribed by the action of…
Simultaneous Orthogonal Planarity
Patrizio Angelini, Steven Chaplick, Sabine Cornelsen +7
We introduce and study the problem: Given planar graphs each with maximum degree 4 and the same vertex set, do they admit an OrthoSEFE, that is, is there…
Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill
Steven Chaplick, Vít Jelínek, Jan Kratochvíl +1
In this paper we study properties of intersection graphs of k-bend paths in the rectangular grid. A k-bend path is a path with at most k 90 degree turns. The class of graphs repres…