{
  "id": "2411.01753",
  "version": "v1",
  "published": "2024-11-04T02:31:35.000Z",
  "updated": "2024-11-04T02:31:35.000Z",
  "title": "Some conjectures on $r$-graphs and equivalences",
  "authors": [
    "Yulai Ma",
    "Eckhard Steffen",
    "Isaak H. Wolf",
    "Junxue Zhang"
  ],
  "comment": "11 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-11-04T02:31:35.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "conjectures",
      "perfect matchings",
      "equivalences",
      "odd set",
      "simple graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}