Matching theory and Barnette's conjecture

DOI10.1016/J.DISC.2022.113249MaRDI QIDQ2099486zbMATHOpenAlexWikidataFDO

Authors Maximilian Gorsky, Raphael Steiner, Sebastian Wiederrecht

Publication date 23 November 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2202.11641

zbMATH Keywords

Barnette's conjecturecubic graphsperfect matchingbipartite graphsmatching theoryPfaffian graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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.

Recommendations

• On Barnette's conjecture
• Remarks on Barnette's conjecture
• A note on Barnette's conjecture
• Barnette's conjecture and Grinberg's formula (Die Barnette'sche Vermutung und die Grinberg'sche Formel)
• Hamiltonian cycles in cubic 3-connected bipartite planar graphs

Cites work

• scientific article; zbMATH DE number 4066957 (Why is no real title available?)
• scientific article; zbMATH DE number 867631 (Why is no real title available?)
• scientific article; zbMATH DE number 3305794 (Why is no real title available?)
• scientific article; zbMATH DE number 3326387 (Why is no real title available?)
• A characterization of convertible (0,1)-matrices
• A computer-assisted proof of the Barnette-Goodey conjecture: not only fullerene graphs are Hamiltonian
• A polynomial algorithm for the extendability problem in bipartite graphs
• Algorithm Theory - SWAT 2004
• Construction for bicritical graphs and \(k\)-extendable bipartite graphs
• Cubic bipartite cyclic 4-connected graphs without Hamiltonian circuits
• Even dicycles
• Graph theory with applications
• Hamiltonian circuits in polytopes with even sided faces
• Hamiltonian cycles in cubic 3-connected bipartite planar graphs
• Hamiltonian cycles in planar cubic graphs with facial 2‐factors, and a new partial solution of Barnette's Conjecture
• Matching structure and the matching lattice
• Matching theory
• Non-Hamiltonian bicubic graphs
• On Hamiltonian Circuits
• On a conjecture of Lovász concerning bricks. I: The characteristic of a matching covered graph
• On n-extendable graphs
• On the 2-factors of bicubic graphs
• Permanents, Pfaffian orientations, and even directed circuits
• Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
• Pólya's permanent problem
• The minimality of the Georges-Kelmans graph
• The smallest 2-connected cubic bipartite planar nonhamiltonian graph
• Thoughts on Barnette's conjecture

Cited in

(5)

• Bipartite matching and Van der Waerden conjecture
• A note on Banach's match box problem
• Beyond the Erdős matching conjecture
• Erdős matching conjecture for almost perfect matchings
• On a conjecture by Gale about one-sided matching problems

This page was built for publication: Matching theory and Barnette's conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2099486)