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

DOI10.37236/9667MaRDI QIDQ2195220zbMATH OpenOpenAlexFDO

Authors Matthieu Rosenfeld

Publication date 8 September 2020

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2006.09094

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: We propose a new proof technique that aims to be applied to the same problems as the Lov'asz 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 $Delta$: a minor improvement on the upper-bound of the non-repetitive number, a $4.25Delta+o(Delta)$ upper-bound on the weak total non-repetitive number and a $Delt{a}^2+frac32^{f}rac13Delt{a}^{frac53}+o(Delt{a}^{frac53})$ 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.

Review text

Summary: We propose a new proof technique that applies 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 chromatic numbers to the maximal degree of a graph. It seems that there should be other interesting applications of the presented approach. In terms of upper-bounds our approach seems to be as strong as entropy-compression, but the proofs are more elementary and shorter. The applications we provide in this paper are upper bounds for graphs of maximal degree at most \(\Delta \): a minor improvement on the upper-bound of the non-repetitive chromatic number, a \(4.25\Delta +o(\Delta)\) upper-bound on the weak total non-repetitive chromatic number, and a \(\Delta^2+\frac{3}{2^{1/3}}\Delta^{5/3}+ o(\Delta^{5/3})\) upper-bound on the total non-repetitive chromatic number of graphs. This last result implies the same upper-bound for the non-repetitive chromatic index of graphs, which improves the best known bound.

Recommendations

• Nonrepetitive colorings of graphs
• Nonrepetitive colorings of graphs
• Nonrepetitive colorings of graphs
• Nonrepetitive colorings of graphs
• Nonrepetitive colorings of graphs of bounded tree-width
• Nonrepetitive colorings of graphs -- a survey
• Notes on nonrepetitive graph colouring
• Degree‐bounded coloring of graphs: Variations on a theme by brooks
• Nonrepetitive vertex colorings of graphs
• Nonrepetitive graph colouring

Cites work

• A constructive proof of the general Lovász local lemma
• Acyclic edge-coloring using entropy compression
• Doubled patterns are 3-avoidable
• Exponential lower bounds for the number of words of uniform length avoiding a pattern
• Further applications of a power series method for pattern avoidance
• New approach to nonrepetitive sequences
• Nonrepetitive colorings of graphs
• Nonrepetitive colorings of graphs
• Nonrepetitive colouring via entropy compression
• Nonrepetitive list colourings of paths
• Nonrepetitive vertex colorings of graphs
• Planar graphs have bounded nonrepetitive chromatic number
• Strict bounds for pattern avoidance
• The local cut lemma
• Total Thue colourings of graphs

Cited in

(20)

• Nonrepetitive list colorings of the integers
• Lower-bounds on the growth of power-free languages over large alphabets
• Nonrepetitively 3-colorable subdivisions of graphs with a logarithmic number of subdivisions per edge
• A general framework for hypergraph coloring
• Avoiding squares over words with lists of size three amongst four symbols
• Nonrepetitive colouring via entropy compression
• Counting colorings of triangle-free graphs
• Graphs of low average degree without independent transversals
• Extensions and reductions of squarefree words
• Optimization in graphical small cancellation theory
• Ann wins the nonrepetitive game over four letters and the erase-repetition game over six letters
• Self-avoiding walks on Cayley graphs through the lens of symbolic dynamics
• Proper conflict-free coloring of graphs with large maximum degree
• Words avoiding tangrams
• The nonrepetitive coloring of grids
• On Vizing's problem for triangle-free graphs
• Finding lower bounds on the growth and entropy of subshifts over countable groups
• Nonrepetitive colorings of \(\mathbb{R}^d\) (extended abstract)
• Acyclic colorings of graphs with obstructions
• Strong parity edge-colorings of graphs

This page was built for publication: Another approach to non-repetitive colorings of graphs of bounded degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2195220)