Consider a graph G with a path P of order n. What conditions force G to also have a long induced path?
In this talk, we will propose a new way to approach this problem, by viewing G as an ordered graph (where the vertices are ordered according to their position on the path P). From this point of view, it is most natural to consider which ordered subgraphs need to be forbidden in order to force the existence of a long induced path. Using this approach we improve or recover several existing resultswith much simpler proofs, in a unified way. We also show that if someforbidden subgraph forces the existence of a long induced path in G,then this induced path has size at least c(log log log n)^1/3$, and ismonotone with respect to P.
This is based on joint work with Jean-Florent Raymond and Louis Esperet.
Julien Duron [ENS Lyon]
https://perso.ens-lyon.fr/julien.duron/
Vérifiez que vous êtes bien inscrits sur le site du [gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres ]
Remarks / Remarques
Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .