31 citations · 55 across the 10 of their papers we have counts for
16 papers
List covering of regular multigraphs with semi-edges
Jan Bok, Jiří Fiala, Nikola Jedličková +2
In line with the recent development in topological graph theory, we are considering undirected graphs that are allowed to contain {\em multiple edges}, {\em loops}, and {\em semi-e…
On Layered Fan-Planar Graph Drawings
Therese Biedl, Steven Chaplick, Jiři Fiala +4
In this paper, we study fan-planar drawings that use layers and are proper, i.e., edges connect adjacent layers. We show that if the embedding of the graph is fixed, then testi…
On the edge-length ratio of 2-trees
Václav Blažej, Jiří Fiala, Giuseppe Liotta
We study planar straight-line drawings of graphs that minimize the ratio between the length of the longest and the shortest edge. We answer a question of Lazard et al. [Theor. Comp…
Reconfiguration Graph for Vertex Colourings of Weakly Chordal Graphs
Carl Feghali, Jiří Fiala
The reconfiguration graph of the -colourings of a graph contains as its vertex set the -colourings of and two colourings are joined by an edge if they differ…
On Vertex- and Empty-Ply Proximity Drawings
Patrizio Angelini, Steven Chaplick, Felice De Luca +7
We initiate the study of the vertex-ply of straight-line drawings, as a relaxation of the recently introduced ply number. Consider the disks centered at each vertex with radius equ…
Gaps in full homomorphism order
Jiří Fiala, Jan Hubička, Yangjing Long
We characterise gaps in the full homomorphism order of graphs.
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…
Fractal property of the graph homomorphism order
Jiří Fiala, Jan Hubička, Yangjing Long +1
We show that every interval in the homomorphism order of finite undirected graphs is either universal or a gap. Together with density and universality this "fractal" property contr…
Fixed parameter complexity of distance constrained labeling and uniform channel assignment problems
Jiří Fiala, Tomáš Gavenčiak, Dušan Knop +2
We study computational complexity of the class of distance-constrained graph labeling problems from the fixed parameter tractability point of view. The parameters studied are neigh…
3-connected Reduction for 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 coverings in which this homomorphism is prescribed by an actio…
Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree
Steven Chaplick, Jiří Fiala, Pim van 't Hof +2
A homomorphism from a graph G to a graph H is locally bijective, surjective, or injective if its restriction to the neighborhood of every vertex of G is bijective, surjective, or i…
Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs
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 in which this locally bijective homomorphism is prescri…
Universality of intervals of line graph order
Jiří Fiala, Jan Hubička, Yangjing Long
We prove that for every the homomorphism order of the class of line graphs of finite graphs with maximal degree is universal. This means that every finite or countabl…
Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs
Hajo Broersma, Jiří Fiala, Petr A. Golovach +3
Hung and Chang showed that for all k>=1 an interval graph has a path cover of size at most k if and only if its scattering number is at most k. They also showed that an interval gr…
The packing chromatic number of the square lattice is at least 12
Jan Ekstein, Jiří Fiala, Přemysl Holub +1
The packing chromatic number of a graph is the smallest integer such that the vertex set can be partitioned into disjoint classes , where ver…
The k-in-a-path problem for claw-free graphs
Jiri Fiala, Marcin Kaminski, Bernard Lidicky +1
Testing whether there is an induced path in a graph spanning k given vertices is already NP-complete in general graphs when k=3. We show how to solve this problem in polynomial tim…