PDF

Discussiones Mathematicae Graph Theory 33(1) (2013) 133-137
DOI: https://doi.org/10.7151/dmgt.1643

Dedicated to M. Borowiecki on the occasion of his 70th birthday

A Note on Barnette's Conjecture

Jochen Harant Institut für Mathematik, TU Ilmenau D-98684 Ilmenau, Germany

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.

Keywords: planar graph, Hamilton cycle, Barnette's Conjecture

2010 Mathematics Subject Classification: 05C38, 05C40, 05C45.

References

[1]	D. Barnette, Conjecture 5, Recent Problems in Combinatorics, W.T. Tutte, (Ed.), Academic Press, New York, 1969, p. 343.
[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.
[3]	J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (MacMillan Co., New York, 1976).
[4]	R. Diestel, Graph Theory, Springer, Graduate Texts in Mathematics 173(2000).
[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.
[6]	B. Grünbaum, Polytopes, graphs and complexes, Bull. Amer. Math. Soc. 76 (1970) 1131--1201, doi: 10.1090/S0002-9904-1970-12601-5.
[7]	A. Hertel, Hamiltonian cycles in sparse graphs, Master?s Thesis, University of Toronto, 2004.
[8]	A. Hertel, A survey & strengthening of Barnette's Conjecture, University of Toronto, 2005.
[9]	J.D. Horton, A counterexample to Tutte's conjecture, in [3], p. 240.
[10]	T.R. Jensen and B. Toft, Graph Coloring Problems, J. Wiley & Sons ( New York, 1995) page 45, doi: 10.1002/9781118032497 .
[11]	A.K. Kelmans, Constructions o.
[12]	A.K. Kelmans, Graph planarity and related topics, Contemp. Math. 147 (1993) 635--667, doi: 10.1090/conm/147/01205.
[13]	A.K. Kelmans, Konstruktsii kubicheskih dvudolnyh 3-Svyaznyh bez Gamiltonovyh tsiklov, Sb. Tr. VNII Sistem. Issled. 10 (1986) 64--72.
[14]	A.K. Kelmans, Kubicheskie dvudolnye tsiklicheski 4-Svyaznye grafy bez Gamiltonovyh tsiklov, Usp. Mat. Nauk 43(3) (1988) 181--182.
[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]	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]	S.K. Stein, B-sets and coloring problems, Bull. Amer. Math. Soc. 76 (1970) 805--806, doi: 10.1090/S0002-9904-1970-12559-9.
[18]	S.K. Stein, B-sets and planar maps, Pacific. J. Math. 37 (1971) 217--224.
[19]	P.G. Tait, Listing?s topologie, Phil. Mag. 17 (1884) 30--46.
[20]	W.T. Tutte, On Hamiltonian circuits, J. London Math. Soc. 21 (1946) 98--101, doi: 10.1112/jlms/s1-21.2.98.
[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.

Received 14 March 2012
Revised 15 August 2012
Accepted 20 August 2012