Source author record

Ján Mazák

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

Catalog footprint

Research overview

3works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

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.

preprint2013arXiv

Cubic graphs with large circumference deficit

The circumference $c(G)$ of a graph $G$ is the length of a longest cycle. By exploiting our recent results on resistance of snarks, we construct infinite classes of cyclically $4$ -, $5$ - and $6$ -edge-connected cubic graphs with circumference ratio $c(G)/|V(G)|$ bounded from above by $0.876$ , $0.960$ and $0.990$ , respectively. In contrast, the dominating cycle conjecture implies that the circumference ratio of a cyclically $4$ -edge-connected cubic graph is at least $0.75$ . In addition, we construct snarks with large girth and large circumference deficit, solving Problem 1 proposed in [J. Hägglund and K. Markström, On stable cycles and cycle double covers of graphs with large circumference, Disc. Math. 312 (2012), 2540--2544].

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.