Source author record

Edita Máčajová

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

8works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Disjoint odd circuits in a bridgeless cubic graph can be quelled by a single perfect matching

Let $G$ be a bridgeless cubic graph. The Berge--Fulkerson Conjecture (1970s) states that $G$ admits a list of six perfect matchings such that each edge of $G$ belongs to exactly two of these perfect matchings. If answered in the affirmative, two other recent conjectures would also be true: the Fan--Raspaud Conjecture (1994), which states that $G$ admits three perfect matchings such that every edge of $G$ belongs to at most two of them; and a conjecture by Mazzuoccolo (2013), which states that $G$ admits two perfect matchings whose deletion yields a bipartite subgraph of $G$ . It can be shown that given an arbitrary perfect matching of $G$ , it is not always possible to extend it to a list of three or six perfect matchings satisfying the statements of the Fan--Raspaud and the Berge--Fulkerson conjectures, respectively. In this paper, we show that given any $1^+$ -factor $F$ (a spanning subgraph of $G$ such that its vertices have degree at least 1) and an arbitrary edge $e$ of $G$ , there always exists a perfect matching $M$ of $G$ containing $e$ such that $G\setminus (F\cup M)$ is bipartite. Our result implies Mazzuoccolo's conjecture, but not only. It also implies that given any collection of disjoint odd circuits in $G$ , there exists a perfect matching of $G$ containing at least one edge of each circuit in this collection.

preprint2022arXiv

Girth, oddness, and colouring defect of snarks

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 graph has defect $0$ if and only if it is $3$ -edge-colourable, this invariant can measure how much a cubic graph differs from a $3$ -edge-colourable graph. Our aim is to examine the relationship of colouring defect to oddness, an extensively studied measure of uncolourability of cubic graphs, defined as the smallest number of odd circuits in a $2$ -factor. We show that there exist cyclically $5$ -edge-connected snarks (cubic graphs with no $3$ -edge-colouring) of oddness $2$ and arbitrarily large colouring defect. This result is achieved by means of a construction of cyclically $5$ -edge-connected snarks with oddness $2$ and arbitrarily large girth. The fact that our graphs are cyclically $5$ -edge-connected significantly strengthens a similar result of Jin and Steffen (2017), which only guarantees graphs with cyclic connectivity at most $3$ . At the same time, our result improves Kochol's original construction of snarks with large girth (1996) in that it provides infinitely many nontrivial snarks of any prescribed girth $g\ge 5$ , not just girth at least~ $g$ .

preprint2020arXiv

Cubic graphs that cannot be covered with four perfect matchings

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 graph in question is $3$ -edge-colourable, the rest of cubic graphs falls into two classes: those that can be covered with four perfect matchings, and those that need at least five. Cubic graphs that require more than four perfect matchings to cover their edges are particularly interesting as potential counterexamples to several profound and long-standing conjectures including the celebrated cycle double cover conjecture. However, so far they have been extremely difficult to find. In this paper we build a theory that describes coverings with four perfect match\-ings as flows whose flow values and outflow patterns form a configuration of six lines spanned by four points of the 3-dimensional projective space $\mathbb{P}_3(\mathbb{F}_2)$ in general position. This theory provides powerful tools for investigation of graphs that do not admit such a cover and offers a great variety of methods for their construction. As an illustrative example we produce a rich family of snarks (nontrivial cubic graphs with no $3$ -edge-colouring) that cannot be covered with four perfect matchings. The family contains all previously known graphs with this property.

preprint2020arXiv

Perfect matching index vs. circular flow number of a cubic graph

The perfect matching index of a cubic graph $G$ , denoted by $π(G)$ , is the smallest number of perfect matchings that cover all the edges of $G$ . According to the Berge-Fulkerson conjecture, $π(G)\le5$ for every bridgeless cubic graph~ $G$ . The class of graphs with $π\ge 5$ is of particular interest as many conjectures and open problems, including the famous cycle double cover conjecture, can be reduced to it. Although nontrivial examples of such graphs are very difficult to find, a few infinite families are known, all with circular flow number $Φ_c(G)=5$ . It has been therefore suggested [Electron. J. Combin. 23 (2016), $\#$ P3.54] that $π(G)\ge 5$ might imply $Φ_c(G)\ge 5$ . In this article we dispel these hopes and present a family of cyclically $4$ -edge-connected cubic graphs of girth at least $5$ (snarks) with $π\ge 5$ and $Φ_c\le 4+\frac23$ .

preprint2016arXiv

Nowhere-zero flows on signed eulerian graphs

This paper is devoted to a detailed study of nowhere-zero flows on signed eulerian graphs. We generalise the well-known fact about the existence of nowhere-zero $2$ -flows in eulerian graphs by proving that every signed eulerian graph that admits an integer nowhere-zero flow has a nowhere-zero $4$ -flow. We also characterise signed eulerian graphs with flow number $2$ , $3$ , and $4$ , as well as those that do not have an integer nowhere-zero flow. Finally, we discuss the existence of nowhere-zero $A$ -flows on signed eulerian graphs for an arbitrary abelian group~ $A$ .

preprint2016arXiv

Odd decompositions of eulerian graphs

We prove that an eulerian graph $G$ admits a decomposition into $k$ closed trails of odd length if and only if and it contains at least $k$ pairwise edge-disjoint odd circuits and $k\equiv |E(G)|\pmod{2}$ . We conjecture that a connected $2d$ -regular graph of odd order with $d\ge 1$ admits a decomposition into $d$ odd closed trails sharing a common vertex and verify the conjecture for $d\le 3$ . The case $d=3$ is crucial for determining the flow number of a signed eulerian graph which is treated in a separate paper (arXiv:1408.1703v2). The proof of our conjecture for $d=3$ is surprisingly difficult and calls for the use of signed graphs as a convenient technical tool.

preprint2016arXiv

The chromatic number of a signed graph

In 1982, Zaslavsky introduced the concept of a proper vertex colouring of a signed graph $G$ as a mapping $ϕ\colon V(G)\to \mathbb{Z}$ such that for any two adjacent vertices $u$ and $v$ the colour $ϕ(u)$ is different from the colour $σ(uv)ϕ(v)$ , where is $σ(uv)$ is the sign of the edge $uv$ . The substantial part of Zaslavsky's research concentrated on polynomial invariants related to signed graph colourings rather than on the behaviour of colourings of individual signed graphs. We continue the study of signed graph colourings by proposing the definition of a chromatic number for signed graphs which provides a natural extension of the chromatic number of an unsigned graph. We establish the basic properties of this invariant, provide bounds in terms of the chromatic number of the underlying unsigned graph, investigate the chromatic number of signed planar graphs, and prove an extension of the celebrated Brooks theorem to signed graphs.

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].

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.

Edita Máčajová

Research overview

Is this your work?

8 publications

Disjoint odd circuits in a bridgeless cubic graph can be quelled by a single perfect matching

Girth, oddness, and colouring defect of snarks

Cubic graphs that cannot be covered with four perfect matchings

Perfect matching index vs. circular flow number of a cubic graph

Nowhere-zero flows on signed eulerian graphs

Odd decompositions of eulerian graphs

The chromatic number of a signed graph

Cubic graphs with large circumference deficit

See the researcher in context

Building this map preview