论文标题
无环着色参数的改进边界
Improved bounds for acyclic coloring parameters
论文作者
论文摘要
图形的{\ em cyclic彩色编号}是正确染色顶点所需的最少颜色，因此其循环都不具有两种颜色。 {\ em无环色索引}是边缘着色的类似图参数。我们首先表明无环色指数最多为$2δ-1$，其中$δ$是图的最大程度。然后，我们表明，对于所有$ε> 0 $，对于$δ$足够大（取决于$ε$），该图的无环色数最多是$ \ lceil（4^{ - 1/3} +ε）δ^{4/3} {4/3} \ rceil +δ +δ +δ +1 $。这两种结果都改善了以前连续进步的长链。两者都是算法，从某种意义上说，这些颜色是通过随机算法生成的。以前的随机算法假定有足够的颜色可用性以确定性确定性，并使用其他颜色以随机的方式处理双重循环。相比之下，我们的算法最初会产生不一定合适的色素。它仅旨在避免在周期遍历中的所有边缘或顶点的所有对或顶点的循环都是同质的（相同的颜色）。当达到此目标时，算法会检查适当性，并在必要时重复直到达到适当性。因此，获得了颜色数量的节省。
The {\em acyclic chromatic number} of a graph is the least number of colors needed to properly color its vertices so that none of its cycles has only two colors. The {\em acyclic chromatic index} is the analogous graph parameter for edge colorings. We first show that the acyclic chromatic index is at most $2Δ-1$, where $Δ$ is the maximum degree of the graph. We then show that for all $ε>0$ and for $Δ$ large enough (depending on $ε$), the acyclic chromatic number of the graph is at most $\lceil(4^{-1/3} +ε) Δ^{4/3} \rceil +Δ+ 1$. Both results improve long chains of previous successive advances. Both are algorithmic, in the sense that the colorings are generated by randomized algorithms. Previous randomized algorithms assume the availability of enough colors to guarantee properness deterministically and use additional colors in dealing with the bichromatic cycles in a randomized fashion. In contrast, our algorithm initially generates colorings that are not necessarily proper; it only aims at avoiding cycles where all pairs of edges, or vertices, that are one edge, or vertex, apart in a traversal of the cycle are homochromatic (of the same color). When this goal is reached, the algorithm checks for properness and if necessary it repeats until properness is attained. Thus savings in the number of colors is attained.
