论文标题
增强了具有独立性第二的图形的Erdős-LovászTihany猜想
Enhancing the Erdős-Lovász Tihany Conjecture for graphs with independence number two
论文作者
论文摘要
令$ s \ ge2 $和$ t \ ge2 $为整数。图$ g $是$（s，t）$ - \ emph {分解}，如果$ v（g）$可以将$ v（g）$划分为两个集合$ s $和$ t $，从而使$χ（g [s]）\ geq s $和$χ（g [t]）\ geq t $。著名的Erdős-LovászTihany从1968年的猜想指出，每个图形$ g $的色度$χ（g）= S+T-1 $都大于其集团数字$ω（g）$是$（s，t）$ - 可覆盖。在本文中，我们证明了Erdős-LovászTihany猜想的增强版本，该图表具有第二个独立性。也就是说，对于每个图$ g $，$χ（g）= s+t-1>ω（g）+1 $ is $（s，t+1）$ - 可分配。有一些例子表明，这种结果是最好的。
Let $s\ge2$ and $t\ge2$ be integers. A graph $G$ is $(s,t)$-\emph{splittable} if $V(G)$ can be partitioned into two sets $S$ and $T$ such that $χ(G[S])\geq s$ and $χ(G[T])\geq t$. The well-known Erdős-Lovász Tihany Conjecture from 1968 states that every graph $G$ whose chromatic number $χ(G)=s+t-1$ is more than its clique number $ω(G)$ is $(s,t)$-splittable. In this paper, we prove an enhanced version of the Erdős-Lovász Tihany Conjecture for graphs with independence number two. That is, for every graph $G$ with $χ(G)=s+t-1>ω(G)+1$ is $(s,t+1)$-splittable. There are examples showing that this result is best possible.
