Long induced paths in graphs

DOI10.1016/J.EJC.2016.11.011MaRDI QIDQ518170zbMATH OpenOpenAlexFDO

Authors L. Esperet, Laetitia Lemoine, Frédéric Maffray

Publication date 28 March 2017

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.06836

zbMATH Keywords

interval graphs3-connected planar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Connectivity (05C40)

Abstract: We prove that every 3-connected planar graph on $n$ vertices contains an induced path on $Omega(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 $Omega(sqrtlogn)$ vertices. We conjecture that for any $k$, there is a contant $c(k)$ such that any $k$-degenerate graph with a path on $n$ vertices also contains an induced path on $Omega((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.

Recommendations

• Long induced paths and cycles in Kneser graphs
• Long induced paths in 3-connected planar graphs
• Long induced paths in minor-closed graph classes and beyond
• Some results on graphs without long induced paths
• Some results on graphs without long induced paths
• Estimating the number of graphs containing very long induced paths
• Long paths and large cycles in finite graphs
• A characterization of graphs without long induced paths
• Graphs containing finite induced paths of unbounded length
• Long paths and cycles in tough graphs

Cites work

• Graphs on surfaces
• Linear time algorithm for computing a small biclique in graphs without long induced paths
• Long induced paths in 3-connected planar graphs
• Lower and upper bounds for long induced paths in 3-connected planar graphs
• Sparsity. Graphs, structures, and algorithms

Cited in

(12)

• Long path connectivity of regular graphs
• Long induced paths in 3-connected planar graphs
• Estimating the number of graphs containing very long induced paths
• Lower and upper bounds for long induced paths in 3-connected planar graphs
• Lower and upper bounds for long induced paths in 3-connected planar graphs
• Long induced paths in minor-closed graph classes and beyond
• Short proofs for long induced paths
• Finding an induced path that is not a shortest path
• Sparse graphs without long induced paths
• On exact solution approaches for the longest induced path problem
• Some results on graphs without long induced paths
• Schnyder Woods and long induced paths in 3-connected planar graphs

This page was built for publication: Long induced paths in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q518170)