On finding hamiltonian cycles in Barnette graphs
From MaRDI portal
Publication:6419640
DOI10.3233/FI-222139zbMATH Open1518.68246arXiv2212.02668MaRDI QIDQ6419640FDOQ6419640
Authors: Behrooz Bagheri Gh., Tomás Feder, Herbert Fleischner, Carlos Subi 
Publication date: 5 December 2022
Abstract: In this paper, we deal with hamiltonicity in planar cubic graphs G having a facial 2-factor Q via (quasi) spanning trees of faces in G/Q and study the algorithmic complexity of finding such (quasi) spanning trees of faces. Moreover, we show that if Barnette's Conjecture is false, then hamiltonicity in 3-connected planar cubic bipartite graphs is an NP-complete problem.
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45)
This page was built for publication: On finding hamiltonian cycles in Barnette graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6419640)
