2022/02/23 by Maximilian Gorsky, Raphael Steiner, Gorsky, Maximilian +3 · 1 citation
Computer Science · Mathematics · #05C10 #05C45 #05C70 #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Graph theory and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2202.11641
openalex publication_date 2022/02/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.