2022
Martin Milanič (University of Primorska, Koper, Slovenia)
https://osebje.famnit.upr.si/~martin.milanic/
"Shifting paths to avoidable ones"
Monday May 30, 2022 on ZOOM, 15:30 Israel time (UTC+3), University of Haifa, Israel
(18:00 India; 13:30 UK; 14:30 France; 9:30 Rio and Buenos Aires ; 8:30 New York; 7:30 Chicago)
For zoom link, please send email to Martin Golumbic <golumbic@cs.haifa.ac.il>
with Subject: Uri Peled Memorial Lecture 2022
Abstract:
An extension of an induced path P in a graph G is an induced path P’ such that deleting the endpoints of P’ results in P. An induced path in a graph is said to be avoidable if each of its extensions is contained in an induced cycle. In 2019, Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius conjectured that every graph that contains an induced k‐vertex path also contains an avoidable induced path of the same length, and proved the result for k = 2. The case k = 1 was known much earlier, due to the work of Ohtsuki, Cheung, and Fujisawa in 1976. The conjecture was proved for all k in 2020 by Bonamy, Defrain, Hatzel, and Thiebaut.
Using a similar approach, we strengthen their result from a reconfiguration point of view. Namely, we show that in every graph, each induced path can be transformed to an avoidable one by a sequence of shifts, where two induced k‐vertex paths are shifts of each other if their union is an induced path with k + 1 vertices. We also obtain analogous results for not necessarily induced paths and for walks. In contrast, the statement cannot be extended to trails or to isometric paths.
This is joint work with Vladimir Gurvich, Matjaž Krnc, and Mikhail Vyalyi.
For zoom link, please send email to Martin Golumbic <golumbic@cs.haifa.ac.il> with Subject: Peled Memorial Lecture 2022
Martin Charles Golumbic, University of Haifa, Israel
Colloquium d’Informatique de Sorbonne Université
Tuesday 8 June 2021 18:00 in Paris; 19:00 in Israel; 12:00 noon in New York
ZOOM link is on the official poster at -- https://www.lip6.fr/colloquium/?guest=Golumbic