Topic:Erdos-Lovasz Tihany Conjecturefor graphs with forbidden holes
Speaker: Professor Song Zixia
Event date: 12/21/2018
Event time: 10:00 a.m.
Venue: Lecture Hall 1506, Building 9
Sponsor: School of Mathematics and Statistics, Institute of Science and Technology
Abstract: Aholein a graphis an induced cycle of length at least $4$.Let $s\ge2$ and $t\ge2$ be integers.A graph $G$ is \dfn{$(s,t)$-splittable} if$V(G)$ can be partitioned into two sets $S$ and $T$ such that $\chi(G[S ]) \ges$ and $\chi(G[T ]) \ge t$.
The well-knownErd\H{o}s-Lov\'asz Tihany Conjecture from 1968 states that everygraph $G$ with $\omega(G) < \chi(G) = s +t - 1$ is $(s,t)$-splittable.
This conjecture is hard,andfew related results are known.However, it has been verified to be true forline graphs, quasi-line graphs, and graphs with independence number $2$. Inthis talk, we will present some recent progress onErd\H{o}s-Lov\'asz Tihany Conjecture.