Lower and upper bounds for long induced paths in 3-connected planar graphs

摘要

Let G be a 3-connected planar graph with n vertices and let p(G) be the maximum number of vertices of an induced subgraph of G that is a path. Substantially improving previous results, we prove that p(G) >= n. To demonstrate the tightness of this bound, we notice that the above inequality implies p(G) is an element of Omega((log(2) n)(1-epsilon)), where epsilon is any positive constant smaller than 1, and describe an infinite family of planar graphs for which p(G) is an element of 0 (log n). As a byproduct of our research, we prove a result of independent interest: Every 3-connected planar graph with n vertices contains an induced subgraph that is outerplanar and connected and that contains at least 3 root n vertices. The proofs in the paper are constructive and give rise to 0 (n)-time algorithms. (C) 2016 Elsevier B.V. All rights reserved.