报告题目：Strengthening the Erd{\H o}s-Lov{\'a}sz Tihany conjecture for line graphs of multigraphs
报告人：王涛副教授，河南大学
报告时间：2024年10月19日（周六）14:30-15:30
会议地点：20-306
摘要：The Ed{\H o}s-Lov{\'a}sz Tihany Conjecture states that if a graph $H$ has chromatic number $\chi(H) = s + t - 1$ and clique number $\omega(H) < \chi(H)$, then the vertex set of $H$ can be partitioned into two subsets, each induces a subgraph with chromatic numbers at least $s$ and $t$, where $s, t \geq 2$. This conjecture has been proven for specific small cases and certain graph classes, such as line graphs and quasi-line graphs. In this paper, we prove that if the line graph $\textsf{Line}(G)$ of a multigraph $G$ satisfies $\chi(\textsf{Line}(G)) = s + t - 1 > \omega(\textsf{Line}(G))$, then $G$ contains a multi-star $S$ of size $s$ such that $\chi(\textsf{Line}(G) - S) \geq t + \ell$, where $s, t$ and $\ell$ are integers with $\ell \geq 1$ and
\[
t \geq s \geq
\begin{cases}
2\ell + 3, & \text{if $\ell = 1$}; \\[0.3cm]
\frac{3 + \sqrt{5}}{2}\ell + \frac{3 + \sqrt{5}}{2}, & \text{otherwise}.
\end{cases}
\]
Our results improve upon the previous bounds on $s$ established by Wang and Yu (J. Graph Theory 101 (1) (2022) 134--141).
报告人简介：王涛，河南大学数学与统计学院副教授，硕士生导师。2009年6月获得南开大学理学博士学位。2013年9月至2014年9月，曾赴伊利诺伊大学香槟校区（UIUC）做访问学者。发表学术论文40余篇，主持完成国家自然科学基金两项。目前主要从事图染色及相关问题研究。