A planar 3-connected graph G is essentially 4-connected if, for any 3-separator S of G, one component of the graph obtained from G by removing S is a single vertex. Jackson and Wormald proved that an essentially 4-connected planar graph on n vertices contains a cycle C such that [...] . For a cubic essentially 4-connected planar graph G, Grünbaum with Malkevitch, and Zhang showed that G has a cycle on at least ¾ n vertices. In the present paper the result of Jackson and Wormald is improved. Moreover, new lower bounds on the length of a longest cycle of G are presented if G is an essentially 4-connected planar graph of maximum degree 4 or G is an essentially 4-connected maximal planar graph.
@article{bwmeta1.element.doi-10_7151_dmgt_1875,
author = {Igor Fabrici and Jochen Harant and Stanislav Jendro\v l},
title = {On Longest Cycles in Essentially 4-Connected Planar Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {36},
year = {2016},
pages = {565-575},
zbl = {1339.05073},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1875}
}
Igor Fabrici; Jochen Harant; Stanislav Jendroľ. On Longest Cycles in Essentially 4-Connected Planar Graphs. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 565-575. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1875/
[1] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008).
[2] I. Fabrici, J. Harant and S. Jendroľ, Paths of low weight in planar graphs, Discuss. Math. Graph Theory 28 (2008) 121-135. doi:10.7151/dmgt.1396[Crossref] | Zbl 1155.05010
[3] B. Grünbaum and J. Malkevitch, Pairs of edge-disjoint Hamilton circuits, Aequationes Math. 14 (1976) 191-196. doi:10.1007/BF01836218[Crossref] | Zbl 0331.05118
[4] B. Jackson and N.C. Wormald, Longest cycles in 3-connected planar graphs, J. Combin. Theory Ser. B 54 (1992) 291-321. doi:10.1016/0095-8956(92)90058-6[Crossref] | Zbl 0696.05031
[5] D.P. Sanders, On paths in planar graphs, J. Graph Theory 24 (1997) 341-345. doi:10.1002/(SICI)1097-0118(199704)24:4<341::AID-JGT6>3.0.CO;2-O[Crossref]
[6] C. Thomassen, A theorem on paths in planar graphs, J. Graph Theory 7 (1983) 169-176. doi:10.1002/jgt.3190070205[Crossref]
[7] W.T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc. 82 (1956) 99-116. doi:10.1090/S0002-9947-1956-0081471-8[Crossref] | Zbl 0070.18403
[8] C.-Q. Zhang, Longest cycles and their chords, J. Graph Theory 11 (1987) 521-529. doi:10.1002/jgt.3190110409[Crossref]