2 citations · 2 across the 6 of their papers we have counts for
9 papers · 1 filter
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,…
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…