On Barnette’s conjecture and the $$H^{+-}$$ H + - property

Jan Florek ()
Additional contact information
Jan Florek: University of Economics

Journal of Combinatorial Optimization, 2016, vol. 31, issue 3, No 1, 943-960

Abstract: Abstract Let $$\mathcal{B}$$ B denote the class of all 3-connected cubic bipartite plane graphs. A conjecture of Barnette states that every graph in $$\mathcal{B}$$ B has a Hamilton cycle. A cyclic sequence of big faces is a cyclic sequence of different faces, each bounded by at least six edges, such that two faces from the sequence are adjacent if and only if they are consecutive in the sequence. Suppose that $${F_1, F_2, F_3}$$ F 1 , F 2 , F 3 is a proper 3-coloring of the faces of $$G^*\in \mathcal{B}$$ G ∗ ∈ B . We prove that if every cyclic sequence of big faces of $$G^*$$ G ∗ has a face belonging to $$F_1$$ F 1 and a face belonging to $$F_2$$ F 2 , then $$G^*$$ G ∗ has the following properties: $$H^{+-}$$ H + - : If any two edges are chosen on the same face, then there is a Hamilton cycle through one and avoiding the other, $$H^{--}$$ H - - : If any two edges are chosen which are an even distance apart on the same face, then there is a Hamilton cycle that avoids both. Moreover, let $$X$$ X and $$Y$$ Y partition the set of big faces of $$G^*$$ G ∗ such that all such faces of $$F_1$$ F 1 are in $$X$$ X and all such faces of $$F_2$$ F 2 are in $$Y$$ Y . We prove that if every cyclic sequence of big faces has a face belonging to $$X$$ X and a face belonging to $$Y$$ Y , then $$G^*$$ G ∗ has a Hamilton cycle.

Keywords: Barnette’s conjecture; Hamilton cycle; Kelman’s property; Induced tree; 05C45; 05C05 (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-014-9797-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:31:y:2016:i:3:d:10.1007_s10878-014-9797-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-014-9797-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().