论文标题
用禁止的几乎两分子图的彩色图
Coloring graphs with forbidden almost bipartite subgraphs
论文作者
论文摘要
Alon，Krivelevich和Sudakov于1999年推测，对于每个有限图$ f $，都存在数量$ c（f）$，因此每当$ f uq（c（f） + o（f） + o（f） + o（f） + o（f） + o（f） +loguδ$每当$ g $是$ f $ f $ f $ f $ f $ f $ f $ f $ f $ freme $δ$时。到目前为止，Alon，Krivelevich和Sudakov本身已经验证了该猜想的最大类连接的图形$ F $，它包括几乎两部分的图形（即完整三方图$ k_ {1，t，t，t，t，t，t，t，t，t，t，t，t，t，t，t，t，t，t，t，t，t，t，t，t，t，t，t，t，t} $的\ in \ mathbb {n} $的$ t} $）。但是，即使对于此类图，$ c（f）$的最佳值仍然未知。 Bollobás使用随机的常规图显示，当$ f $包含一个周期时，$ c（f）\ geq 1/2 $。另一方面，Davies，Kang，Pirot和Sereni最近建立了$ c（k_ {1，t，t，t}）\ leq t $的上限。我们将其改进到一个均匀的常数，显示了每条几乎两部分图$ f $的$ c（f）\ leq 4 $。令人惊讶的是，在所有已知的猜想案例中，绑定了$ f $。在DP色（也称为对应着色）的设置中，我们还建立了一个更通用的版本，并考虑了结果的一些算法后果。
Alon, Krivelevich, and Sudakov conjectured in 1999 that for every finite graph $F$, there exists a quantity $c(F)$ such that $χ(G) \leq (c(F) + o(1)) Δ/ \logΔ$ whenever $G$ is an $F$-free graph of maximum degree $Δ$. The largest class of connected graphs $F$ for which this conjecture has been verified so far, by Alon, Krivelevich, and Sudakov themselves, comprises the almost bipartite graphs (i.e., subgraphs of the complete tripartite graph $K_{1,t,t}$ for some $t \in \mathbb{N}$). However, the optimal value for $c(F)$ remains unknown even for such graphs. Bollobás showed, using random regular graphs, that $c(F) \geq 1/2$ when $F$ contains a cycle. On the other hand, Davies, Kang, Pirot, and Sereni recently established an upper bound of $c(K_{1,t,t}) \leq t$. We improve this to a uniform constant, showing $c(F) \leq 4$ for every almost bipartite graph $F$. This surprisingly makes the bound independent of $F$ in all the known cases of the conjecture. We also establish a more general version of our bound in the setting of DP-coloring (also known as correspondence coloring) and consider some algorithmic consequences of our results.
