Geodesic
On Longest Cycles in Essentially 4-Connected Planar Graphs
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 3, pp. 565-575.

Voir la notice de l'article provenant de la source Library of Science

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 |V(C)| ≥2n+4/5. For a cubic essentially 4-connected planar graph G, Grünbaum with Malkevitch, and Zhang showed that G has a cycle on at least 3/4 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.
Keywords: planar graph, longest cycle 
@article{DMGT_2016_36_3_a4,
     author = {Fabrici, Igor and Harant, Jochen and Jendro\v{l}, Stanislav},
     title = {On {Longest} {Cycles} in {Essentially} {4-Connected} {Planar} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {565--575},
     publisher = {mathdoc},
     volume = {36},
     number = {3},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a4/}
}
TY  - JOUR
AU  - Fabrici, Igor
AU  - Harant, Jochen
AU  - Jendroľ, Stanislav
TI  - On Longest Cycles in Essentially 4-Connected Planar Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 565
EP  - 575
VL  - 36
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a4/
LA  - en
ID  - DMGT_2016_36_3_a4
ER  - 
%0 Journal Article
%A Fabrici, Igor
%A Harant, Jochen
%A Jendroľ, Stanislav
%T On Longest Cycles in Essentially 4-Connected Planar Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 565-575
%V 36
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a4/
%G en
%F DMGT_2016_36_3_a4
Fabrici, Igor; Harant, Jochen; Jendroľ, Stanislav. On Longest Cycles in Essentially 4-Connected Planar Graphs. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 3, pp. 565-575. http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a4/

[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

[3] B. Grünbaum and J. Malkevitch, Pairs of edge-disjoint Hamilton circuits, Aequationes Math. 14 (1976) 191-196. doi:10.1007/BF01836218

[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

[5] D.P. Sanders, On paths in planar graphs, J. Graph Theory 24 (1997) 341-345. doi:10.1002/(SICI)1097-0118(199704)24:43.0.CO;2-O

[6] C. Thomassen, A theorem on paths in planar graphs, J. Graph Theory 7 (1983) 169-176. doi:10.1002/jgt.3190070205

[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

[8] C.-Q. Zhang, Longest cycles and their chords, J. Graph Theory 11 (1987) 521-529. doi:10.1002/jgt.3190110409