• This event has passed.

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

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

Zoom ID: 869 4632 6610 (ibsdimag)

Speaker

Daniel Cranston
Department of Computer Science, Virginia Commonwealth University
https://www.people.vcu.edu/~dcranston/

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:
Thursday, November 5, 2020
Time:
10:00 AM - 11:00 AM KST
Event Category:
Event Tags:

Venue

Zoom ID: 869 4632 6610 (ibsdimag)

Organizer

O-joung Kwon (권오정)
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209