{
  "id": "2202.11641",
  "version": "v1",
  "published": "2022-02-23T17:21:40.000Z",
  "updated": "2022-02-23T17:21:40.000Z",
  "title": "Matching Theory and Barnette's Conjecture",
  "authors": [
    "Maximilian Gorsky",
    "Raphael Steiner",
    "Sebastian Wiederrecht"
  ],
  "comment": "24 pages, 4 figures",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Barnette's Conjecture claims that all cubic, 3-connected, planar, bipartite graphs are Hamiltonian. We give a translation of this conjecture into the matching-theoretic setting. This allows us to relax the requirement of planarity to give the equivalent conjecture that all cubic, 3-connected, Pfaffian, bipartite graphs are Hamiltonian. A graph, other than the path of length three, is a brace if it is bipartite and any two disjoint edges are part of a perfect matching. Our perspective allows us to observe that Barnette's Conjecture can be reduced to cubic, planar braces. We show a similar reduction to braces for cubic, 3-connected, bipartite graphs regarding four stronger versions of Hamiltonicity. Note that in these cases we do not need planarity. As a practical application of these results, we provide some supplements to a generation procedure for cubic, 3-connected, planar, bipartite graphs discovered by Holton et al. [Hamiltonian Cycles in Cubic 3-Connected Bipartite Planar Graphs, JCTB, 1985]. These allow us to check whether a graph we generated is a brace.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-02-23T17:21:40.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C10",
      "68R10",
      "05C45",
      "05C70",
      "G.2.2",
      "F.2.2"
    ],
    "keywords": [
      "bipartite graphs",
      "matching theory",
      "barnettes conjecture claims",
      "bipartite planar graphs",
      "disjoint edges"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 24,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}