Seminar| Institute of Mathematical Sciences
Time：14:00-15:00, October 22 Tuesday
Location：Room S408, IMS
Speaker: : Hehui Wu/SCMS, Fudan University
Abstract:The Hall ratio of a graph $G$ is the maximum of $|V(H)|/\alpha(H)$ over all subgraphs $H$ of $G$. Clearly, the Hall ratio of a graph is a lower bound for the fractional chromatic number. It has been asked whether conversely, the fractional chromatic number is upper bounded by a function of the Hall ratio. We answer this question in negative, by showing two results of independent interest regarding 1-subdivisions (the 1-subdivision of a graph is obtained by subdividing each edge exactly once):For every $c>0$, every graph of sufficiently large average degree contains as a subgraph the 1-subdivision of a graph of fractional chromatic number at least $c$.
For every $d>0$, there exists a graph $G$ of average degree at least $d$ such that every graph whose 1-subdivision appears as a subgraph of $G$ has Hall ratio at most 18.
This is joint work with Zdenek Dvorak and Patrice Ossona de Mendez.