论文标题
改进的局部密度绘制图表的过程
An improved procedure for colouring graphs of bounded local density
论文作者
论文摘要
在假设跨越任何邻域的边数最多是$（1-σ）\binomΔ{2} $的最大程度$δ$的色度图$δ$的图表的变化数限制的限制。通过此界限实现的颜色的降低的领先术语最好是$σ\ to0 $。作为两个后果，我们以两个长期且研究的图形构想，Erdős-nešetùilil的猜想和里德的猜想，推进了最新技术的状态。我们证明，对于任何图形$ g $，强大的$ g $最高$1.772Δ^2 $，具有足够大的最大程度$δ$。我们证明，对于任何图$ g $，具有$ g $的色度最多为$ \ lceil 0.881（δ+1）+0.119Ω\ rceil $，具有clique number $ω$，并且足够大的最高度$δ$。此外，我们还展示了如何在Codegree最多是$（1-σ）δ$的附加假设下对方法进行调整，并确定可以被认为可以被认为是vu的猜想的首先进展。
We develop an improved bound for the chromatic number of graphs of maximum degree $Δ$ under the assumption that the number of edges spanning any neighbourhood is at most $(1-σ)\binomΔ{2}$ for some fixed $0<σ<1$. The leading term in the reduction of colours achieved through this bound is best possible as $σ\to0$. As two consequences, we advance the state of the art in two longstanding and well-studied graph colouring conjectures, the Erdős-Nešetřil conjecture and Reed's conjecture. We prove that the strong chromatic index is at most $1.772Δ^2$ for any graph $G$ with sufficiently large maximum degree $Δ$. We prove that the chromatic number is at most $\lceil 0.881(Δ+1)+0.119ω\rceil$ for any graph $G$ with clique number $ω$ and sufficiently large maximum degree $Δ$. Additionally, we show how our methods can be adapted under the additional assumption that the codegree is at most $(1-σ)Δ$, and establish what may be considered first progress towards a conjecture of Vu.
