On Barnette's conjecture

DOI10.1016/J.DISC.2010.01.018zbMATH Open1218.05084arXiv1208.4332OpenAlexW2056802753WikidataQ28111748 ScholiaQ28111748MaRDI QIDQ968428FDOQ968428

Jan Florek

Publication date: 5 May 2010

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

Abstract: A conjecture of Barnette states that every 3-connected cubic bipartite plane graph has a Hamilton cycle, which is equivalent to the statement that every simple even plane triangulation admits a partition of its vertex set into two subsets so that each induces a tree. Let $G$ be a simple even plane triangulation and suppose that $V_1,V_2,V_3$ is a 3-coloring of the vertex set of $G$. Let $B_i$, $i=1,2,3$, be the set of all vertices in $V_i$ of the degree at least 6. We prove that if induced graphs $G[B_{1}cup{B}_2]$ and $G[B_{1}cup{B}_3]$ are acyclic, then the following properties are satisfied: [6pt] (1) For every path $abc$ there is possible to partition the vertex set of $G$ into two subsets so that each induces a tree, and one of them contains the edge $ab$ and avoids the vertex $c$, [6pt] (2) For every path $abc$ with vertices $a$, $c$ of the same color there is possible to partition the vertex set of $G$ into two subsets so that each induces a tree, and one of them contains the path $abc$.

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

Recommendations

• A note on Barnette's conjecture
• Remarks on Barnette's conjecture
• Hamiltonian cycles in planar cubic graphs with facial 2‐factors, and a new partial solution of Barnette's Conjecture
• Necessary condition for cubic planar 3-connected graph to be non-Hamiltonian with proof of Barnette's conjecture
• Barnette's conjecture and Grinberg's formula (Die Barnette'sche Vermutung und die Grinberg'sche Formel)

zbMATH Keywords

Barnette's conjectureHamilton cycle2-factor

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

Cites Work

• Hamiltonian circuits in polytopes with even sided faces
• Hamiltonicity of planar cubic multigraphs
• B-sets and planar maps
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Hamiltonian cycles in cubic 3-connected bipartite planar graphs
• Convex Polytopes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Hamiltonicity of cubic Cayley graphs
• A Note on the Vertex Arboricity of a Graph

Cited In (16)

• Title not available (Why is that?)
• On a Conjecture of Butler
• On Barnette's conjecture and the \(H^{+-}\) property
• A note on Barnette's conjecture
• Recent advances on the Hamiltonian problem: survey III
• On a problem of Barnes and Duncan
• Title not available (Why is that?)
• Remarks on Barnette's conjecture
• Minimal reducible bounds for planar graphs
• Title not available (Why is that?)
• Hamiltonian cycles in some family of cubic 3-connected plane graphs
• On Finding Hamiltonian Cycles in Barnette Graphs
• Hamiltonian cycles in planar cubic graphs with facial 2‐factors, and a new partial solution of Barnette's Conjecture
• Are all simple 4-polytopes Hamiltonian?
• On some conjectures on cubic 3-connected graphs
• On Hamilton decompositions of prisms over simple 3-polytopes

This page was built for publication: On Barnette's conjecture

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