论文标题
有限程度图的非重复色素的另一种方法
Another approach to non-repetitive colorings of graphs of bounded degree
论文作者
论文摘要
我们提出了一种新的证明技术，该技术旨在应用于与Lovász局部引理或熵压缩方法相同的问题。我们在非重复色彩的上下文中介绍了这种方法，并使用它来改善与图形最大程度不同的非重复数字相关的上限。似乎应该在提出的方法中使用其他有趣的应用。 就上限而言，我们的方法似乎与熵压缩一样强，但是证据更基本和更短。我们在本文中提供的应用是最大程度图的上限，最多是$δ$：在非重复数字的上限上有较小的改进，$4.25δ+O（δ）$上限$ the Botic the Botil Botic Botal非重复效率和A $ δ^2+ \ frac {3} {2^\ frac {1} {3}}Δ^{\ frac {5} {3}}}}}+ o（δ^{\ frac {5} {5} {3}} {3}}} {3}}}}} {3}}）$上的非重复编号上的非重复编号。最后的结果意味着对于非重复索引的相同上限，这改善了最著名的界限。
We propose a new proof technique that aims to be applied to the same problems as the Lovász Local Lemma or the entropy-compression method. We present this approach in the context of non-repetitive colorings and we use it to improve upper-bounds relating different non-repetitive numbers to the maximal degree of a graph. It seems that there should be other interesting applications to the presented approach. In terms of upper-bound our approach seems to be as strong as entropy-compression, but the proofs are more elementary and shorter. The application we provide in this paper are upper bounds for graphs of maximal degree at most $Δ$: a minor improvement on the upper-bound of the non-repetitive number, a $4.25Δ+o(Δ)$ upper-bound on the weak total non-repetitive number and a $ Δ^2+\frac{3}{2^\frac{1}{3}}Δ^{\frac{5}{3}}+ o(Δ^{\frac{5}{3}})$ upper-bound on the total non-repetitive number of graphs. This last result implies the same upper-bound for the non-repetitive index of graphs, which improves the best known bound.
