Online talk: Dan Cranston

Monday, September 28, 3pm ET (8pm BST, 7am Tue NZST)
Dan Cranston, Virginia Commonwealth U
Vertex Partitions into an Independent Set and a Forest with Each Component Small


For each integer $k \ge 2$, we determine a sharp bound on $\text{mad}(G)$ such that $V(G)$ can be partitioned into sets $I$ and $F_k$, where $I$ is an independent set and $G[F_k]$ is a forest in which each component has at most $k$ vertices. For each $k$ we construct an infinite family of examples showing our result is best possible. Hendrey, Norin, and Wood asked for the largest function $g(a,b)$ such that if $\text{mad}(G)<g(a,b)$ then $V(G)$ has a partition into sets $A$ and $B$ such that $\text{mad}(G[A])<a$ and $\text{mad}(G[B])<b$. They specifically asked for the value of $g(1,b)$, which corresponds to the case that $A$ is an independent set. Previously, the only values known were $g(1,4/3)$ and $g(1,2)$. We find the value of $g(1,b)$ whenever $4/3<b<2$. This is joint work with Matthew Yancey.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.