论文标题
在$ k $ - 可油的最大直径上
On the maximum diameter of $k$-colorable graphs
论文作者
论文摘要
ERDS，Pach，Pollack和Tuza [J。组合。理论，b 47，（1989），279-285]猜想，$ k_ {2r} $的直径 - 免费连接的订单$ n $和最低度$δ\ geq 2 $的直径最多是$ \ frac {2（r-1）（r-1）（r-1）（3r + 2）}} {（3r + 2）} {（2r^2-1）{（2r^2-1）{（2r^2-1） $ r \ ge 2 $，如果$δ$是$（R-1）（3R+2）$的倍数。对于每$ r> 1 $和$δ\ ge 2（r-1）$，我们创建$ k_ {2r} $ - 免费图形，最低度$δ$和直径$ \ frac {（6r-5）n} {（6r-5）n} {（2r-1）δ+2r-3}+o（2r-1）Δ+2r-3}+o（o（o（ $δ> 2（R-1）（3R+2）（2R-3）$。本文的其余部分证明了在更强的假设，即$ k $ - 可溶性下的积极结果，而不是$ k_ {k+1} $ - 免费。我们表明，连接的$ k $ - 颜色图的直径具有最低度$ \ geqδ$和订单$ n $的直径最多是$ \ \ weft（3- \ frac {1} {1} {k-1} {k-1} \ right）\ frac {n}δ+o（1）$，而对于$ k = 3 $，则$ \ frac {57n} {23δ}+o \ left（1 \ right）$。
Erdős, Pach, Pollack and Tuza [J. Combin. Theory, B 47, (1989), 279-285] conjectured that the diameter of a $K_{2r}$-free connected graph of order $n$ and minimum degree $δ\geq 2$ is at most $\frac{2(r-1)(3r+2)}{(2r^2-1)}\cdot \frac{n}δ + O(1)$ for every $r\ge 2$, if $δ$ is a multiple of $(r-1)(3r+2)$. For every $r>1$ and $δ\ge 2(r-1)$, we create $K_{2r}$-free graphs with minimum degree $δ$ and diameter $\frac{(6r-5)n}{(2r-1)δ+2r-3}+O(1)$, which are counterexamples to the conjecture for every $r>1$ and $δ>2(r-1)(3r+2)(2r-3)$. The rest of the paper proves positive results under a stronger hypothesis, $k$-colorability, instead of being $K_{k+1}$-free. We show that the diameter of connected $k$-colorable graphs with minimum degree $\geq δ$ and order $n$ is at most $\left(3-\frac{1}{k-1}\right)\frac{n}δ+O(1)$, while for $k=3$, it is at most $\frac{57n}{23δ}+O\left(1\right)$.
