12 citations · 41 across the 15 of their papers we have counts for
22 papers
On covering cubic graphs with three perfect matchings
Edita Máčajová, Ján Mazák
For a bridgeless cubic graph , is the ratio of the maximum number of edges of covered by the union of perfect matchings to . We prove that for any $r\in…
List strong and list normal edge-coloring of (sub)cubic graphs
Borut Lužar, Edita Máčajová, Roman Soták +1
A strong edge-coloring of a graph is a proper edge-coloring, in which the edges of every path of length 3 receive distinct colors; in other words, every pair of edges at distance a…
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…
Three-cuts are a charm: acyclicity in 3-connected cubic graphs
František Kardoš, Edita Máčajová, Jean Paul Zerafa
Let be a bridgeless cubic graph. In 2023, the three authors solved a conjecture (also known as the -Conjecture) made by Mazzuoccolo in 2013: there exist two perfect matchi…
The Frank number and nowhere-zero flows on graphs
Jan Goedgebeur, Edita Máčajová, Jarne Renders
An edge of a graph is called deletable for some orientation if the restriction of to is a strong orientation. Inspired by a problem of Frank, in 2021 Hörsch a…
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…
Disjoint odd circuits in a bridgeless cubic graph can be quelled by a single perfect matching
František Kardoš, Edita Máčajová, Jean Paul Zerafa
Let be a bridgeless cubic graph. The Berge--Fulkerson Conjecture (1970s) states that admits a list of six perfect matchings such that each edge of belongs to exactly tw…
Decomposition of cubic graphs with cyclic connectivity 5
Edita Máčajová, Jozef Rajník
Let be a cyclically -connected cubic graph with a -edge-cut separating into two cyclic components and . We prove that each component can be completed…
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…
Some snarks are worse than others
Edita Máčajová, Giuseppe Mazzuoccolo, Vahan Mkrtchyan +1
Many conjectures and open problems in graph theory can either be reduced to cubic graphs or are directly stated for cubic graphs. Furthermore, it is known that for a lot of problem…
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…
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…
Shorter signed circuit covers of graphs
Tomáš Kaiser, Robert Lukot'ka, Edita Máčajová +1
A signed circuit is a minimal signed graph (with respect to inclusion) that admits a nowhere-zero flow. We show that each flow-admissible signed graph on edges can be covered b…
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…
Cubic graphs with large circumference deficit
Edita Máčajová, Ján Mazák
The circumference of a graph is the length of a longest cycle. By exploiting our recent results on resistance of snarks, we construct infinite classes of cyclically -…
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…
Circular edge-colorings of cubic graphs with girth six
D. Král', E. Mácajová, J. Mazák +1
We show that the circular chromatic index of a (sub)cubic graph with girth at least six is at most 7/2.