Construction of Barnette graphs whose large subgraphs are non-Hamiltonian

[1] T. Akiyama, T. Nishizeki and N. Saiton, NP-compleateness of the Hamiltonian cycle problem for bipartite graphs, Journal Information Processing, 3 (2) (1980), 73–76.Search in Google Scholar

[2] R. Aldred, G. Brinkmann and B. D. McKay, Announcement, March 2000.Search in Google Scholar

[3] D. Barnette, Conjecture 5, In W. T. Tutte ed. Recent Progress in Combinatorics, page 343 Academic press, New York, 1969.Search in Google Scholar

[4] I. Cahit, Algorithmic proof of Barnette’s Conjecture, https://arxiv.org/pdf/0904.3431.pdf (2009).Search in Google Scholar

[5] T. Feder and C. Subi, On Barnette’s Conjecture, Published on internet http://theory.stanford.edu/tomas/bar.ps.Search in Google Scholar

[6] T. Fowler, Reducible Configurations for the Barnett’s conjecture, Unpublished manuscript August 2001.Search in Google Scholar

[7] P. R. Goodey, Hamiltonian circuit in Polytopes with even sided faces, Israel J. Mathematics, 22 (1975) 52–56.Search in Google Scholar

[8] B. Grunbaum, Polytopes, Graphs and Complexes, Bull. Amer. Math. Soc., 76 (1970) 1131–1201.Search in Google Scholar

[9] J. Harant, A Note on Barnette’s Conjecture, Discussiones Mathematicae Graph Theory, 33 (2013) 133–137.Search in Google Scholar

[10] A. Hertel, Hamiltonian Cycle in Sparse Graphs, Master’s thesis, University of Toronto, 2004.Search in Google Scholar

[11] A. Hertel, A survey and strengthening of Barnette’s Conjecture, Department of Computer Science, University of Toronto, 2005.Search in Google Scholar

[12] T. R. Jensen and B. Toft, Graph Coloring Problem, J. Wiley and Sons New York, 1995.10.1002/9781118032497Search in Google Scholar

[13] A. K. Kalmans, Konstruktsii Kubicheskih Dvudolnyh 3-Svyaznyh Bez GamiltonovyhTsiklov, Sb.TrVNiii Sistem, issled., 10 (1986), 64–72.Search in Google Scholar

[14] D. König,Über, Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Mathematische Annalen, 77 (1916), 453–465.10.1007/BF01456961Search in Google Scholar

[15] B. D. McKay, D. A. Holton and B. Manvel, Hamiltonian cycles in cubic 3- connected bipartite planar graphs, J. Combinatorial Theory, Series B, 38 (1985) 279–297.Search in Google Scholar

[16] S. Pirzada, An Introduction to Graph Theory, Universities Press, Orient Blackswan, Hyderabad, 2012.Search in Google Scholar

[17] C. Thomassen, A theorem on paths in planar graphs, J. Graph Theory, 7 (1983), 169–176.10.1002/jgt.3190070205Search in Google Scholar

[18] W. T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc., 82 (1956), 99–116.10.1090/S0002-9947-1956-0081471-8Search in Google Scholar