A sequence of symbols is called square-free if it does not contain a subsequence of the form
proved that there is an infinite square-free sequence consisting of three symbols. Sequences can be thought of as colours on the vertices of a path. The authors examine graph colourings for which the colour sequence is square-free on any path. They obtain the result that the vertices of any
-tree have a colouring of this kind using
. Moreover, they support the conjecture of Alon et al.
that a fixed number of colours suffices for any planar graph. They show that this number is at most 12 for outerplanar graphs and construct some outerplanar graphs which require at least 7 colours. Moreover, they construct planar graphs for which at least 10 colours are needed.