12 citations · 26 across the 13 of their papers we have counts for
19 papers
Strictly critical snarks with girth or cyclic connectivity equal to 6
Ján Mazák, Jozef Rajník, Martin Škoviera
A snark -- connected cubic graph with chromatic index -- is critical if the graph resulting from the removal of any pair of distinct adjacent vertices is -edge-colourable; i…
An 8-flow theorem for signed graphs
Rong Luo, Edita Máčajová, Martin Škoviera +1
We prove that a signed graph admits a nowhere-zero -flow provided that it is flow-admissible and the underlying graph admits a nowhere-zero -flow. When combined with the 4-co…
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…
Morphology of small snarks
Ján Mazák, Jozef Rajník, Martin Škoviera
The aim of this paper is to classify all snarks up to order and explain the reasons of their uncolourability. The crucial part of our approach is a computer-assisted structura…
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…
Strong edge colorings of graphs and the covers of Kneser graphs
Borut Lužar, Edita Mačajová, Martin Škoviera +1
A proper edge coloring of a graph is strong if it creates no bichromatic path of length three. It is well known that for a strong edge coloring of a -regular graph at least $2k-…
Cubic graphs that cannot be covered with four perfect matchings
Edita Máčajová, Martin Škoviera
A conjecture of Berge suggests that every bridgeless cubic graph can have its edges covered with at most five perfect matchings. Since three perfect matchings suffice only when the…
The smallest nontrivial snarks of oddness 4
Jan Goedgebeur, Edita Máčajová, Martin Škoviera
The oddness of a cubic graph is the smallest number of odd circuits in a 2-factor of the graph. This invariant is widely considered to be one of the most important measures of unco…
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…
Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44
Jan Goedgebeur, Edita Máčajová, Martin Škoviera
The family of snarks -- connected bridgeless cubic graphs that cannot be 3-edge-coloured -- is well-known as a potential source of counterexamples to several important and long-sta…
Critical and flow-critical snarks coincide
Edita Máčajová, Martin Škoviera
Over the past twenty years, critical and bicritical snarks have been appearing in the literature in various forms and in different contexts. Two main variants of criticality of sna…
Simple greedy 2-approximation algorithm for the maximum genus of a graph
Michal Kotrbcik, Martin Skoviera
The maximum genus of a graph G is the largest genus of an orientable surface into which G has a cellular embedding. Combinatorially, it coincides with the maximum number o…
The chromatic number of a signed graph
Edita Máčajová, André Raspaud, Martin Škoviera
In 1982, Zaslavsky introduced the concept of a proper vertex colouring of a signed graph as a mapping such that for any two adjacent vertices a…
Characteristic flows on signed graphs and short circuit covers
Edita Macajova, Martin Skoviera
We generalise to signed graphs a classical result of Tutte [Canad. J. Math. 8 (1956), 13--28] stating that every integer flow can be expressed as a sum of characteristic flows of c…
Small snarks with large oddness
Robert Lukotka, Edita Macajova, Jan Mazak +1
We estimate the minimum number of vertices of a cubic graph with given oddness and cyclic connectivity. We prove that a bridgeless cubic graph with oddness other than th…
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…
Chirality Groups of Maps and Hypermaps
Antonio Breda d'Azevedo, Gareth Jones, Roman Nedela +1
Although the phenomenon of chirality appears in many investigations of maps and hypermaps no detailed study of chirality seems to have been carried out. Chirality of maps and hyper…