2024/11/04 by Yulai Ma, Eckhard Steffen, Ma, Yulai +5 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2411.01753
openalex publication_date 2024/11/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An r-regular graph is an r-graph, if every odd set of vertices is connected to its complement by at least r edges. Seymour [On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte.~Proc.~London Math.~Soc.~(3), 38(3): 423-460, 1979] conjectured (1) that every planar r-graph is r-edge colorable and (2) that every r-graph has 2r perfect matchings such that every edge is contained in precisely two of them. We study several variants of these conjectures. A (t,r)-PM is a multiset of t ⋅ r perfect matchings of an r-graph G such that every edge is in precisely t of them. We show that the following statements are equivalent for every t, r ≥ 1: 1. Every planar r-graph has a (t,r)-PM. 2. Every K5-minor-free r-graph has a (t,r)-PM. 3. Every K3,3-minor-free r-graph has a (t,r)-PM. 4. Every r-graph whose underlying simple graph has crossing number at most 1 has a (t,r)-PM.