Source author record

Robert Lukoťka

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO math.OC

Catalog footprint

Research overview

5works

3topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Cubic TSP - a 1.3-approximation

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.

preprint2016arXiv

Weak oddness as an approximation of oddness and resistance in cubic graphs

We introduce weak oddness $ω_{\textrm w}$ , a new measure of uncolourability of cubic graphs, defined as the least number of odd components in an even factor. For every bridgeless cubic graph $G$ , $ρ(G)\leω_{\textrm w}(G)\leω(G)$ , where $ρ(G)$ denotes the resistance of $G$ and $ω(G)$ denotes the oddness of $G$ , so this new measure is an approximation of both oddness and resistance. We demonstrate that there are graphs $G$ satisfying $ρ(G) < ω_{\textrm w}(G) < ω(G)$ , and that the difference between any two of those three measures can be arbitrarily large. The construction implies that if we replace a vertex of a cubic graph with a triangle, then its oddness can decrease by an arbitrarily large amount.

preprint2015arXiv

Short cycle covers on cubic graphs using chosen 2-factor

We show that every bridgeless cubic graph $G$ with $m$ edges has a cycle cover of length at most $1.6 m$ . Moreover, if $G$ does not contain any intersecting circuits of length $5$ , then $G$ has a cycle cover of length $212/135 \cdot m \approx 1.570 m$ and if $G$ contains no $5$ -circuits, then it has a cycle cover of length at most $14/9 \cdot m \approx 1.556 m$ . To prove our results, we show that each $2$ -edge-connected cubic graph $G$ on $n$ vertices has a $2$ -factor containing at most $n/10+f(G)$ circuits of length $5$ , where the value of $f(G)$ only depends on the presence of several subgraphs arising from the Petersen graph. As a corollary we get that each $3$ -edge-connected cubic graph on $n$ vertices has a $2$ -factor containing at most $n/9$ circuits of length $5$ and each $4$ -edge-connected cubic graph on $n$ vertices has a $2$ -factor containing at most $n/10$ circuits of length $5$ .

preprint2014arXiv

Avoiding 5-circuits in a 2-factor of cubic graphs

We show that every bridgeless cubic graph $G$ on $n$ vertices other than the Petersen graph has a 2-factor with at most $2(n-2)/15$ circuits of length $5$ . An infinite family of graphs attains this bound. We also show that $G$ has a 2-factor with at most $n/5.8\overline{3}$ odd circuits. This improves the previously known bound of $n/5.41$ [Lukoťka, Máčajová, Mazák, Škoviera: Small snarks with large oddness, arXiv:1212.3641 [cs.DM] ].

preprint2013arXiv

Maximum 4-degenerate subgraph of a planar graph

A graph $G$ is $k$ -degenerate if it can be transformed into an empty graph by subsequent removals of vertices of degree $k$ or less. We prove that every connected planar graph with average degree $d \ge 2$ has a 4-degenerate induced subgraph containing at least $(38-d)/36$ of its vertices. This shows that every planar graph of order $n$ has a 4-degenerate induced subgraph of order more than $8/9 \cdot n$ . We also consider a local variation of this problem and show that in every planar graph with at least 7 vertices, deleting a suitable vertex allows us to subsequently remove at least 6 more vertices of degree four or less.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.