8 citations · 13 across the 6 of their papers we have counts for
9 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…
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…
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…
Simple cubic graphs with no short traveling salesman tour
Robert Lukoťka, Ján Mazák
Let denote the length of a shortest travelling salesman tour in a graph . We prove that for any , there exists a simple -connected planar cubic graph…
Weak oddness as an approximation of oddness and resistance in cubic graphs
Robert Lukoťka, Ján Mazák
We introduce weak oddness , a new measure of uncolourability of cubic graphs, defined as the least number of odd components in an even factor. For every bridgeless 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 -…
Maximum 4-degenerate subgraph of a planar graph
Robert Lukoťka, Ján Mazák, Xuding Zhu
A graph is -degenerate if it can be transformed into an empty graph by subsequent removals of vertices of degree or less. We prove that every connected planar graph with…
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.