基于熵压缩方法的广义无圈边染色

Generalized Acyclic Edge Coloring with Entropy Compression Method

摘要: 图$G$ 的无圈边染色是一种正常边染色，且染色中不存在双色圈。图$G$ 的广义无圈边染色是在无圈边染色基础上进一步要求不存在双色路。本文借助洛瓦兹(Lovász)局部引理(LLL)与熵压缩方法，得到：对最大度为$\Delta$ 的任意图$G$ ，当$\Delta$ 充分大时，其广义无圈边色数上界为$\left(k-2\right){\left(k-3\right)}^{-\frac{k-3}{k-2}}{\lceil \frac{k}{2}\rceil }^{\frac{1}{k-2}}{\Delta }^{\frac{k-1}{k-2}}+3\Delta$ (其中$k$ 为图$G$ 中路的长度)，该结果为广义无圈边染色问题提供了一个更优的上界。

Abstract: The acyclic edge coloring of a graph $G$ is a proper coloring without bichromatic cycles. The generalized acyclic edge coloring of a graph $G$ is an acyclic edge coloring without bichromatic paths. Based on Lovász Local Lemma (LLL) and the entropy compression method, we concluded that for any graph $G$ with maximum degree $\Delta$ , the generalized acyclic edge chromatic index is at most$\left(k-2\right){\left(k-3\right)}^{-\frac{k-3}{k-2}}{\lceil \frac{k}{2}\rceil }^{\frac{1}{k-2}}{\Delta }^{\frac{k-1}{k-2}}+3\Delta$ ($k$ is the length of paths in the graph $G$ ) when $\Delta$ is large enough, providing a better upper bound for the generalized acyclic edge coloring problem.