pith. sign in

arxiv: 2411.01753 · v2 · pith:WSX36BX3new · submitted 2024-11-04 · 🧮 math.CO

Some conjectures on r-graphs and equivalences

classification 🧮 math.CO
keywords everygraphconjecturesedgegraphsmatchingsminor-freeperfect
0
0 comments X
read the original abstract

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.~\emph{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 \cdot 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 \geq 1$: 1. Every planar $r$-graph has a $(t,r)$-PM. 2. Every $K_5$-minor-free $r$-graph has a $(t,r)$-PM. 3. Every $K_{3,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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.