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/