## Nonrepetitive colorings of line arrangements

### Authors:

- Jarosław Grytczuk,
- Karol Kosiński,
- Michał Zmarz

### Abstract

A sequence is nonrepetitive if no two adjacent segments of are identical. A famous result of Thue from 1906 asserts that there are arbitrarily long nonrepetitive sequences over 3 symbols. We study the following geometric variant of this problem. Given a set of points in the plane and a set of lines, what is the least number of colors needed to color so that every line in is nonrepetitive? If consists of all intersection points of a prescribed set of lines , then we prove that there is such coloring using at most 405 colors. The proof is based on a theorem of Thue and on a result of Alon and Marshall concerning homomorphisms of edge colored planar graphs. We also consider nonrepetitive colorings involving other geometric structures. For instance, a nonrepetitive analog of the famous Hadwiger–Nelson problem is formulated as follows: what is the least number of colors needed to color the plane so that every path of the unit distance graph whose vertices are colinear is nonrepetitive? Using a theorem of Thue we prove that this number is at most .

- Record ID
- WUT791dff00a00745368129a692ff0491d7
- Author
- Journal series
- European Journal of Combinatorics, ISSN 0195-6698
- Issue year
- 2016
- Vol
- 51
- Pages
- 275-279
- Publication size in sheets
- 0.50
- ASJC Classification
- DOI
- DOI:10.1016/j.ejc.2015.05.013 Opening in a new tab
- URL
- https://www.sciencedirect.com/science/article/pii/S0195669815001304?via%3Dihub Opening in a new tab
- Language
- (en) English
- Score (nominal)
- 30
- Score source
- journalList
- Score
- Publication indicators
- = 6; = 4; : 2016 = 1.167; : 2016 (2 years) = 0.786 - 2016 (5 years) =0.828

- Uniform Resource Identifier
- https://repo.pw.edu.pl/info/article/WUT791dff00a00745368129a692ff0491d7/

- URN
`urn:pw-repo:WUT791dff00a00745368129a692ff0491d7`

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or PerishOpening in a new tab system.