Induced paths in sparse graphs

Every induced path is a path, but the converse is not true. However in some classes of graphs (such as, for instance, planar graphs), the existence of a large path implies the existence of a long induced path. In 1982 Galvin, Rival, and Sands proved that such a statement holds in the general setting of graphs excluding a fixed biclique as subgraph. However in several cases their bound can be substantially improved.

In this talk I will present recent results on this topic in several sparse graph classes: graphs of bounded pathwidth, treewidth, degeneracy, and in topological-minor closed graph classes. 

This is joint work with Claire Hilaire and Oscar Defrain.

We look forward to seeing you there!