Another approach to non-repetitive colorings of graphs of bounded degree
share
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+3/2^1/3Δ^5/3+ o(Δ^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.
READ FULL TEXT