On Finding Hamiltonian Cycles in Barnette Graphs

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.

---

Opracowanie rekordu ze środków MNiSW, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).