Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777419 | European Journal of Combinatorics | 2017 | 14 Pages |
Abstract
We prove that every 3-connected planar graph on n vertices contains an induced path on Ω(logn) vertices, which is best possible and improves the best known lower bound by a multiplicative factor of loglogn. We deduce that any planar graph (or more generally, any graph embeddable on a fixed surface) with a path on n vertices, also contains an induced path on Ω(logn) vertices. We conjecture that for any k, there is a positive constant c(k) such that any k-degenerate graph with a path on n vertices also contains an induced path on Ω((logn)c(k)) vertices. We provide examples showing that this order of magnitude would be best possible (already for chordal graphs), and prove the conjecture in the case of interval graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Louis Esperet, Laetitia Lemoine, Frédéric Maffray,