Long induced paths in graphs. (May 2017)

• Record Type: Journal Article
• Authors: Esperet, Louis; Lemoine, Laetitia; Maffray, Frédéric
• Is Part Of: European journal of combinatorics. Volume 62(2017)
• Page Start: 1
• Page End: 14
• Publication Date: 2017-05
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2016.11.011
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: We prove that every 3-connected planar graph on n vertices contains an induced path on Ω ( log n ) vertices, which is best possible and improves the best known lower bound by a multiplicative factor of log log n . 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 Ω ( log n ) 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 Ω ( ( log n ) 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.