Matching theory and Barnette's conjecture

DOI10.1016/J.DISC.2022.113249zbMATH Open1504.05232arXiv2202.11641OpenAlexW4308545206WikidataQ122918692 ScholiaQ122918692MaRDI QIDQ2099486FDOQ2099486

Authors: Maximilian Gorsky, Raphael Steiner, Sebastian Wiederrecht 

Publication date: 23 November 2022

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• On a conjecture of Lovász concerning bricks. I: The characteristic of a matching covered graph
• Pólya's permanent problem
• A characterization of convertible (0,1)-matrices
• Permanents, Pfaffian orientations, and even directed circuits
• Title not available (Why is that?)
• Hamiltonian circuits in polytopes with even sided faces
• Thoughts on Barnette's conjecture
• Graph theory with applications
• Matching theory
• Hamiltonian cycles in cubic 3-connected bipartite planar graphs
• On n-extendable graphs
• Title not available (Why is that?)
• A polynomial algorithm for the extendability problem in bipartite graphs
• The smallest 2-connected cubic bipartite planar nonhamiltonian graph
• Matching structure and the matching lattice
• Title not available (Why is that?)
• Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
• Construction for bicritical graphs and \(k\)-extendable bipartite graphs
• On Hamiltonian Circuits
• Non-Hamiltonian bicubic graphs
• Title not available (Why is that?)
• Even dicycles
• Algorithm Theory - SWAT 2004
• A Computer-Assisted Proof of the Barnette--Goodey Conjecture: Not Only Fullerene Graphs Are Hamiltonian
• On the 2-factors of bicubic graphs
• Cubic bipartite cyclic 4-connected graphs without Hamiltonian circuits
• The minimality of the Georges–Kelmans graph
• Hamiltonian cycles in planar cubic graphs with facial 2‐factors, and a new partial solution of Barnette's Conjecture

Cited In (5)

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

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)