Kevin Hendrey presented his work on the minimum connectivity to force a minor isomorphic to a fixed forest in a large graph at the discrete math seminar

On September 10, 2019, Kevin Hendrey at IBS Discrete Mathematics Group presented his work on the minimum connectivity to force a minor isomorphic to a fixed forest in a large graph. The title of his talk was “The minimum connectivity forcing forest minors in large graphs”.

Kevin Hendrey, The minimum connectivity forcing forest minors in large graphs

Given a graph $G$, we define $\textrm{ex}_c(G)$ to be the minimum value of $t$ for which there exists a constant $N(t,G)$ such that every $t$-connected graph with at least $N(t,G)$ vertices contains $G$ as a minor. The value of $\textrm{ex}_c(G)$ is known to be tied to the vertex cover number $\tau(G)$, and in fact $\tau(G)\leq \textrm{ex}_c(G)\leq \frac{31}{2}(\tau(G)+1)$. We give the precise value of $\textrm{ex}_c(G)$ when $G$ is a forest. In particular we find that $\textrm{ex}_c(G)\leq \tau(G)+2$ in this setting, which is tight for infinitely many forests.