Loading Events

« All Events

:

Daniel Cranston, Vertex Partitions into an Independent Set and a Forest with Each Component Small

November 5 Thursday @ 10:00 AM - 11:00 AM KST

Zoom

Speaker

For each integer $k\ge 2$, we determine a sharp bound on
$\operatorname{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 $\operatorname{mad}(G) < g(a,b)$ then $V(G)$ has a partition into sets $A$ and $B$ such that $\operatorname{mad}(G[A]) < a$ and $\operatorname{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.

Details

Date:
November 5 Thursday
Time:
10:00 AM - 11:00 AM KST
Event Category:
Event Tags:

Venue

Zoom

Organizer

O-joung Kwon (권오정)