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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.