数学科学研究所
Insitute of Mathematical Science

Seminar:1-subdivisions, fractional chromatic number and Hall ratio

Seminar| Institute of Mathematical Sciences

Time14:00-15:00, October 22 Tuesday

LocationRoom 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.


地址:上海市浦东新区华夏中路393号
邮编:201210
上海市徐汇区岳阳路319号8号楼
200031(岳阳路校区)