2019-08-12 Jaehoon Kim (김재훈), Tree decompositions of graphs without large bipartite holes

IBS Discrete Mathematics Group
IBS One-Day Conference on Extremal Graph Theory
Jaehoon Kim (김재훈), Tree decompositions of graphs without large bipartite holes
August 12 2019, Monday @ 11:00 AM ~ 12:00 PM
Room B232, IBS (기초과학연구원)
Speaker
Jaehoon Kim (김재훈)
KAIST, Korea
sites.google.c...
A recent result of Condon, Kim, Kühn and Osthus implies that for any $r \geq (1/2 + o(1))n$, an $n$-vertex almost $r$-regular graph $G$ has an approximate decomposition into any collections of $n$-vertex bounded degree trees. In this talk, we prove that a similar result holds for an almost $\alpha n$-regular graph $G$ with any positive $\alpha$ and a collection of bounded degree trees on at most $(1-o(1))n$ vertices if $G$ does not contain large bipartite holes. This result is sharp in the sense that it is necessary to exclude large bipartite holes and we cannot hope for an approximate decomposition into $n$-vertex trees. This is joint work with Younjin Kim and Hong Liu.