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\"unbaum constructed a graph $G$ with $Gal(G)=3$. Very recently, Long, Milans, and Munaro, proved that $Gal(G)\leq 8n^{ { 3}/{ 4}}$. This was the first sublinear upper bound on $Gal(G)$ in terms of $n$. We improve their bound to $Gal(G)\leq 5 n^{ { 2}/{ 3}}$. We also tighten a more general result of Long et al. For a multigraph $M$ on m edges, we prove that if the set $L(M,G)$ of maximum $M$-subdivisions in $G$ is pairwise intersecting and $n\geq m^{ 6}$, then $G$ has a set of vertices with size at most $5 n^{ { 2}/{ 3}}$ that meets every $Q\in \mathcal{ L}(M,G)$
Categories: math.CO