Improved upper-bounds on longest-path and maximal-subdivision transversals

Let G be a connected graph on n vertices. The Gallai number
Gal(G) of G is the size of the smallest set of vertices that meets
every maximum path in G. Grünbaum constructed a graph G with Gal(G) =
3. Very recently, Long, Milans, and Munaro, proved that Gal(G) ≤
8n^3/4. This was the first sub-linear upper bound on Gal(G) in terms
of n. We improve their bound to Gal(G) ≤ 5n^2/3. We also tighten a
more general result of Long et al. For a multigraph M, we prove that
if the set L(M, G) of maximum M-subdivisions in G is pairwise
intersecting and n ≥ m^6, then G has a set of vertices with size at
most 5n^2/3 that meets every Q ∈ L(M, G).

This talk should be accessible to current graph theory students. At
the time we made our initial breakthrough, Eric Ren (the co-author) was an
undergraduate graph theory student.