A Note on Barnette’s Conjecture

Jochen Harant

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 1, page 133-137
  • ISSN: 2083-5892

Abstract

top
Barnette conjectured that each planar, bipartite, cubic, and 3-connected graph is hamiltonian. We prove that this conjecture is equivalent to the statement that there is a constant c > 0 such that each graph G of this class contains a path on at least c|V (G)| vertices.

How to cite

top

Jochen Harant. "A Note on Barnette’s Conjecture." Discussiones Mathematicae Graph Theory 33.1 (2013): 133-137. <http://eudml.org/doc/267635>.

@article{JochenHarant2013,
abstract = {Barnette conjectured that each planar, bipartite, cubic, and 3-connected graph is hamiltonian. We prove that this conjecture is equivalent to the statement that there is a constant c > 0 such that each graph G of this class contains a path on at least c|V (G)| vertices.},
author = {Jochen Harant},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {planar graph; Hamilton cycle; Barnette’s Conjecture; Barnette's conjecture},
language = {eng},
number = {1},
pages = {133-137},
title = {A Note on Barnette’s Conjecture},
url = {http://eudml.org/doc/267635},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Jochen Harant
TI - A Note on Barnette’s Conjecture
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 1
SP - 133
EP - 137
AB - Barnette conjectured that each planar, bipartite, cubic, and 3-connected graph is hamiltonian. We prove that this conjecture is equivalent to the statement that there is a constant c > 0 such that each graph G of this class contains a path on at least c|V (G)| vertices.
LA - eng
KW - planar graph; Hamilton cycle; Barnette’s Conjecture; Barnette's conjecture
UR - http://eudml.org/doc/267635
ER -

References

top
  1. [1] D. Barnette, Conjecture 5, Recent Problems in Combinatorics, W.T. Tutte, (Ed.), Academic Press, New York, 1969, p. 343. 
  2. [2] J.A. Bondy and S.C. Locke, Relative lengths of paths and cycles in 3-connected graphs, Discrete Math. 33 (1981) 111-122. doi:10.1016/0012-365X(81)90159-X[WoS][Crossref] Zbl0448.05044
  3. [3] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (MacMillan Co., New York, 1976). Zbl1226.05083
  4. [4] R. Diestel, Graph Theory, Springer, Graduate Texts in Mathematics 173(2000). 
  5. [5] M.N. Ellingham and J.D. Horton, Non-hamiltonian 3-connected cubic bipartite graphs, J. Combin. Theory (B) 34 (1983) 330-333. doi:10.1016/0095-8956(83)90046-1[Crossref] Zbl0516.05033
  6. [6] B. Grünbaum, Polytopes, graphs and complexes, Bull. Amer. Math. Soc. 76 (1970) 1131-1201. doi:10.1090/S0002-9904-1970-12601-5[Crossref] Zbl0211.25001
  7. [7] A. Hertel, Hamiltonian cycles in sparse graphs, Masters Thesis, University of Toronto, 2004. 
  8. [8] A. Hertel, A survey & strengthening of Barnette’s Conjecture, University of Toronto, 2005. 
  9. [9] J.D. Horton, A counterexample to Tutte’s conjecture, in [3], p. 240. 
  10. [10] T.R. Jensen and B. Toft, Graph Coloring Problems, J. Wiley & Sons ( New York, 1995) page 45. doi:10.1002/9781118032497[Crossref] 
  11. [11] A.K. Kelmans, Constructions of cubic bipartite and 3-connected graphs without Hamiltonian cycles, Analiz Zadach Formirovaniya i Vybora Alternativ, VNIISI, Moscow 10 (1986) 64-72, in Russian. (see also AMS Translations, Series 2 158 (1994) 127-140, A.K. Kelmans, (Ed.)) 
  12. [12] A.K. Kelmans, Graph planarity and related topics, Contemp. Math. 147 (1993) 635-667. doi:10.1090/conm/147/01205[Crossref] 
  13. [13] A.K. Kelmans, Konstruktsii kubicheskih dvudolnyh 3-Svyaznyh bez Gamiltonovyh tsiklov, Sb. Tr. VNII Sistem. Issled. 10 (1986) 64-72. 
  14. [14] A.K. Kelmans, Kubicheskie dvudolnye tsiklicheski 4-Svyaznye grafy bez Gamiltonovyh tsiklov, Usp. Mat. Nauk 43(3) (1988) 181-182. 
  15. [15] M. Król, On a sufficient and necessary condition of 3-colorability of a planar graph, I, Prace Nauk. Inst. Mat. Fiz. Teoret. 6 (1972) 37-40. 
  16. [16] M. Król, On a sufficient and necessary condition of 3-colorability of a planar graph, II, Prace Nauk. Inst. Mat. Fiz. Teoret. 9 (1973) 49-54. 
  17. [17] S.K. Stein, B-sets and coloring problems, Bull. Amer. Math. Soc. 76 (1970) 805-806. doi:10.1090/S0002-9904-1970-12559-9[Crossref] Zbl0194.56004
  18. [18] S.K. Stein, B-sets and planar maps, Pacific. J. Math. 37 (1971) 217-224. Zbl0194.56101
  19. [19] P.G. Tait, Listings topologie, Phil. Mag. 17 (1884) 30-46. 
  20. [20] W.T. Tutte, On Hamiltonian circuits, J. London Math. Soc. 21 (1946) 98-101. doi:10.1112/jlms/s1-21.2.98[Crossref] 
  21. [21] W.T. Tutte, On the 2-factors of bicubic graphs, Discrete Math. 1 (1971) 203-208. doi:10.1016/0012-365X(71)90027-6[Crossref] 

NotesEmbed ?

top

You must be logged in to post comments.