Sharp bounds on the size of long induced paths in graphs

Prelegent(ci)

Julien Duron

Język referatu

angielski

Termin

5 grudnia 2025 14:15

Pokój

p. 5060

Seminarium

Seminarium "Algorytmika"

---

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.

---