3 citations · 10 across the 6 of their papers we have counts for
8 papers
Circular flow number of Goldberg snarks
Robert Lukoťka
A circular nowhere-zero -flow on a bridgeless graph is an orientation of the edges and an assignment of real values from to the edges in such a way that the sum o…
Short cycle covers of cubic graphs and intersecting 5-circuits
Robert Lukoťka
A cycle cover of a graph is a collection of cycles such that each edge of the graph is contained in at least one of the cycles. The length of a cycle cover is the sum of all cycle…
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…
Nowhere-zero flows in signed graphs: A survey
Tomáš Kaiser, Edita Rollová, Robert Lukot'ka
We survey known results related to nowhere-zero flows and related topics, such as circuit covers and the structure of circuits of signed graphs. We include an overview of several d…
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 TSP - a 1.3-approximation
Barbora Candráková, Robert Lukoťka
We prove that every simple bridgeless cubic graph with n >= 8 vertices has a travelling salesman tour of length at most 1.3n - 2, which can be constructed in polynomial time.
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…