On Longest Cycles in Essentially 4-Connected Planar Graphs

Igor Fabrici, Jochen Harant, and Stanislav Jendroľ. "On Longest Cycles in Essentially 4-Connected Planar Graphs." Discussiones Mathematicae Graph Theory 36.3 (2016): 565-575. <http://eudml.org/doc/285784>.

@article{IgorFabrici2016,
abstract = {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.},
author = {Igor Fabrici, Jochen Harant, Stanislav Jendroľ},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {planar graph; longest cycle},
language = {eng},
number = {3},
pages = {565-575},
title = {On Longest Cycles in Essentially 4-Connected Planar Graphs},
url = {http://eudml.org/doc/285784},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Igor Fabrici
AU - Jochen Harant
AU - Stanislav Jendroľ
TI - On Longest Cycles in Essentially 4-Connected Planar Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 3
SP - 565
EP - 575
AB - 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.
LA - eng
KW - planar graph; longest cycle
UR - http://eudml.org/doc/285784
ER -