Jean-Florent Raymond, Long induced paths in minor-closed graph classes and beyond
Zoom ID: 869 4632 6610 (ibsdimag)In 1982 Galvin, Rival, and Sands proved that in $K_{t,t}$-subgraph free graphs (t being fixed), the existence of a path of order n guarantees the existence of an induced path of order f(n), for some (slowly) increasing function f. The problem of obtaining good lower-bounds for f for specific graph classes was investigated decades later …