Sharp bounds on the size of long induced paths in graphs

Speaker(s)

Julien Duron

Language of the talk

English

Date

Dec. 5, 2025, 2:15 p.m.

Room

room 5060

Seminar

Seminar Algorithms

---

Given a graph containing a path on n vertices, what guarantees can we have on the maximal size of an induced path?

In 1982 Galvin, Rival and Sands proved that there is an unbounded function f such that a weakly sparse graph containing a path on n vertices also contains a induced path on f(n) vertices. Since then, a number of  classes of graphs have been studied in order to find the exact dependence between these two sizes.

By looking at ordered graphs with forbidden substructures, we propose a framework generalizing and unifying most of the known results, and we will in particular answer the question for planar graphs.

---