Zobrazeno 1 - 10
of 91
pro vyhledávání: '"Mačajová, Edita"'
A strong edge-coloring of a graph is a proper edge-coloring, in which the edges of every path of length 3 receive distinct colors; in other words, every pair of edges at distance at most 2 must be colored differently. The least number of colors neede
Externí odkaz:
http://arxiv.org/abs/2410.01049
We prove that a signed graph admits a nowhere-zero $8$-flow provided that it is flow-admissible and the underlying graph admits a nowhere-zero $4$-flow. When combined with the 4-color theorem, this implies that every flow-admissible bridgeless planar
Externí odkaz:
http://arxiv.org/abs/2402.12883
We introduce a new invariant of a cubic graph - its regular defect - which is defined as the smallest number of edges left uncovered by any collection of three perfect matchings that have no edge in common. This invariant is a modification of defect,
Externí odkaz:
http://arxiv.org/abs/2312.13638
Let $G$ be a bridgeless cubic graph. In 2023, the three authors solved a conjecture (also known as the $S_4$-Conjecture) made by Mazzuoccolo in 2013: there exist two perfect matchings of $G$ such that the complement of their union is a bipartite subg
Externí odkaz:
http://arxiv.org/abs/2309.06944
The colouring defect of a cubic graph is the smallest number of edges left uncovered by any set of three perfect matchings. While $3$-edge-colourable graphs have defect $0$, those that cannot be $3$-edge-coloured (that is, snarks) are known to have d
Externí odkaz:
http://arxiv.org/abs/2308.13639
An edge $e$ of a graph $G$ is called deletable for some orientation $o$ if the restriction of $o$ to $G-e$ is a strong orientation. Inspired by a problem of Frank, in 2021 H\"orsch and Szigeti proposed a new parameter for $3$-edge-connected graphs, c
Externí odkaz:
http://arxiv.org/abs/2305.02133
A long-standing conjecture of Berge suggests that every bridgeless cubic graph can be expressed as a union of at most five perfect matchings. This conjecture trivially holds for $3$-edge-colourable cubic graphs, but remains widely open for graphs tha
Externí odkaz:
http://arxiv.org/abs/2210.13234
Publikováno v:
J. Combin. Theory Ser. B 160, 1--14 (2023). Share Link: https://authors.elsevier.com/a/1gKfKLpTmV29P
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 othe
Externí odkaz:
http://arxiv.org/abs/2204.10021
Autor:
Máčajová, Edita, Rajník, Jozef
Let $G$ be a cyclically $5$-connected cubic graph with a $5$-edge-cut separating $G$ into two cyclic components $G_1$ and $G_2$. We prove that each component $G_i$ can be completed to a cyclically $5$-connected cubic graph by adding three vertices, u
Externí odkaz:
http://arxiv.org/abs/2107.09756
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 inva
Externí odkaz:
http://arxiv.org/abs/2106.12205