Another approach to non-repetitive colorings of graphs of bounded degree

preprint2020arXivOpen access

Abstract

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(Δ)4.25Δ+o(Δ) upper-bound on the weak total non-repetitive number and a Δ2+3213Δ53+o(Δ53) Δ^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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.