TY - GEN
AB - Thomassen [Problem 1 in Factorizing regular graphs, J. Combin. Theory Ser. B, 141 (2020), 343-351] asked whether every r-edge-connected r-regular graph of even order has r−2 pairwise disjoint perfect matchings. We show that this is not the case if r≡2 mod 4. Together with a recent result of Mattiolo and Steffen [Highly edge-connected regular graphs without large factorizable subgraphs, J. Graph Theory, 99 (2022), 107-116] this solves Thomassen's problem for all even r.
It turns out that our methods are limited to the even case of Thomassen's problem. We then prove some equivalences of statements on pairwise disjoint perfect matchings in highly edge-connected regular graphs, where the perfect matchings contain or avoid fixed sets of edges.
Based on these results we relate statements on pairwise disjoint perfect matchings of 5-edge-connected 5-regular graphs to well-known conjectures for cubic graphs, such as the Fan-Raspaud Conjecture, the Berge-Fulkerson Conjecture and the 5-Cycle Double Cover Conjecture.
AU - Ma, Yulai
AU - Mattiolo, Davide
AU - Steffen, Eckhard
AU - Wolf, Isaak Hieronymus
ID - 32184
T2 - arXiv:2206.10975
TI - Pairwise disjoint perfect matchings in r-edge-connected r-regular graphs
ER -
TY - GEN
AB - For 0≤t≤r let m(t,r) be the maximum number s such that every t-edge-connected r-graph has s pairwise disjoint perfect matchings. There are only a few values of m(t,r) known, for instance m(3,3)=m(4,r)=1, and m(t,r)≤r−2 for all t≠5, and m(t,r)≤r−3 if r is even. We prove that m(2l,r)≤3l−6 for every l≥3 and r≥2l.
AU - Ma, Yulai
AU - Mattiolo, Davide
AU - Steffen, Eckhard
AU - Wolf, Isaak Hieronymus
ID - 33661
T2 - arXiv:2208.14835
TI - Edge-connectivity and pairwise disjoint perfect matchings in regular graphs
ER -
TY - JOUR
AU - Steffen, Eckhard
AU - Wolf, Isaak Hieronymus
ID - 31543
IS - 3
JF - Graphs and Combinatorics
KW - Discrete Mathematics and Combinatorics
KW - Theoretical Computer Science
SN - 0911-0119
TI - Even Factors in Edge-Chromatic-Critical Graphs with a Small Number of Divalent Vertices
VL - 38
ER -
TY - GEN
AB - The paper studies edge-coloring of signed multigraphs and extends classical Theorems of Shannon and König to signed multigraphs. We prove that the chromatic index of a signed multigraph (G,σG) is at most ⌊32Δ(G)⌋. Furthermore, the chromatic index of a balanced signed multigraph (H,σH) is at most Δ(H)+1 and the balanced signed multigraphs with chromatic index Δ(H) are characterized.
AU - Steffen, Eckhard
AU - Wolf, Isaak Hieronymus
ID - 32185
T2 - arXiv:2206.11052
TI - Bounds for the chromatic index of signed multigraphs
ER -