11 citations · 23 across the 21 of their papers we have counts for
25 papers
Graph covers and semi-covers: Who is stronger?
Jan Kratochvil, Roman Nedela
The notion of graph cover, also known as locally bijective homomorphism, is a discretization of covering spaces known from general topology. It is a pair of incidence-preserving ve…
Cubic graphs with colouring defect 3
Ján Karabáš, Edita Máčajová, Roman Nedela +1
The colouring defect of a cubic graph is the smallest number of edges left uncovered by any set of three perfect matchings. While -edge-colourable graphs have defect , those…
Decycling cubic graphs
Roman Nedela, Michaela Seifrtová, Martin Škoviera
A set of vertices of a graph is said to be decycling if its removal leaves an acyclic subgraph. The size of a smallest decycling set is the decycling number of . Generally,…
Berge's conjecture for cubic graphs with small colouring defect
Ján Karabáš, Edita Máčajová, Roman Nedela +1
A long-standing conjecture of Berge suggests that every bridgeless cubic graph can be expressed as a union of at most five perfect matchings. This conjecture trivially holds for $3…
The Jacobian of a graph and graph automorphisms
István Estélyi, Ján Karabáš, Alexander Mednykh +1
In the present paper we investigate the faithfulness of certain linear representations of groups of automorphisms of a graph in the group of symmetries of the Jacobian of .…
Computing equivalence classes of finite group actions on orientable surfaces: A dynamic survey
Ján Karabáš, Roman Nedela, Mária Skyvová
This paper focuses on the classification of classes of topological equivalence of finite group actions on Riemann surfaces. By the Riemann-Hurwitz bound, there are just finitely ma…
Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable
Vikraman Arvind, Roman Nedela, Ilia Ponomarenko +1
The computational complexity of the graph isomorphism problem is considered to be a major open problem in theoretical computer science. It is known that testing isomorphism of chor…
Girth, oddness, and colouring defect of snarks
Ján Karabáš, Edita Máčajová, Roman Nedela +1
The colouring defect of a cubic graph, introduced by Steffen in 2015, is the minimum number of edges that are left uncovered by any set of three perfect matchings. Since a cubic gr…
On a representation of the automorphism group of a graph in a unimodular group
István Estelyi, Ján Karabáš, Alexander Mednykh +1
We investigate a representation of the automorphism group of a connected graph in the group of unimodular matrices of dimension , where is the Betti number of grap…
Automorphism groups of maps in linear time
Ken-ichi Kawarabayashi, Bojan Mohar, Roman Nedela +1
By a map we mean a -cell decomposition of a closed compact surface, i.e., an embedding of a graph such that every face is homeomorphic to an open disc. Automorphism of a map can…
The Weisfeiler-Leman dimension of distance-hereditary graphs
Alexander L. Gavrilyuk, Roman Nedela, Ilia Ponomarenko
A graph is said to be distance-hereditary if the distance function in every connected induced subgraph is the same as in the graph itself. We prove that the ordinary Weisfeiler-Lem…
Testing isomorphism of circular-arc graphs in polynomial time
Roman Nedela, Ilia Ponomarenko, Peter Zeman
A graph is said to be circular-arc if the vertices can be associated with arcs of a circle so that two vertices are adjacent if and only if the corresponding arcs overlap. It is pr…
Complete regular dessins and skew-morphisms of cyclic groups
Yan-Quan Feng, Kan Hu, Roman Nedela +2
A dessin is a 2-cell embedding of a connected -coloured bipartite graph into an orientable closed surface. A dessin is regular if its group of orientation- and colour-preserving…
Regular dessins uniquely determined by a nilpotent automorphism group
Naer Wang, Roman Nedela, Kan Hu
It is well known that the automorphism group of a regular dessin is a two-generator finite group, and the isomorphism classes of regular dessins with automorphism groups isomorphic…
Nilpotent groups of class two which underly a unique regular dessin
Kan Hu, Roman Nedela, Naer Wang
A dessin is an embedding of connected bipartite graph into an oriented closed surface. A dessin is regular if its group of colour- and orientation-preserving automorphisms acts tra…
Complete regular dessins of odd prime power order
Kan Hu, Naer Wang, Roman Nedela
A dessin is a -cell embedding of a connected -coloured bipartite graph into an orientable closed surface. A dessin is regular if its group of colour- and orientation-preservi…
Recognizing and testing isomorphism of Cayley graphs over an abelian group of order in polynomial time
Roman Nedela, Ilia Ponomarenko
We construct a polynomial-time algorithm that given a graph with vertices ( is prime), finds (if any) a Cayley representation of over the group $C_2\times C_2\times…
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…
Totally symmetric dessins with nilpotent automorphism groups of class three
Na-Er Wang, Roman Nedela, Kan Hu
A dessin is a 2-cell embedding of a connected bipartite graph into an orientable closed surface. An automorphism of a dessin is a permutation of the edges of the underlying graph w…
Nilpotent dessins: Decomposition theorem and classification of the abelian dessins
Kan Hu, Roman Nedela, Na-Er Wang
A map is a 2-cell decomposition of an orientable closed surface. A dessin is a bipartite map with a fixed colouring of vertices. A dessin is regular if its group of colour- and ori…
Jordan-like characterization of automorphism groups of planar graphs
Pavel Klavík, Roman Nedela, Peter Zeman
We investigate automorphism groups of planar graphs. The main result is a complete recursive description of all abstract groups that can be realized as automorphism groups of plana…
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…
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…
2-Groups that factorise as products of cyclic groups, and regular embeddings of complete bipartite graphs
Shaofei Du, Gareth Jones, Jin Ho Kwak +2
We classify those 2-groups G which factorise as a product of two disjoint cyclic subgroups A and B, transposed by an automorphism of order 2. The case where G is metacyclic having…