Some results on square-free colorings of graphs

A sequence of symbols a_1,a_2… is called square-free if it does not contain a subsequence of consecutive terms of the form x_1,… x_m,x_1,… x_m. A century ago Thue showed that there exist arbitrarily long square-free sequences using only three symbols. Sequences can be thought of as colors on the vertices or edges of a path.

Conversely one can form sequences from a vertex or edge coloring of a graph in different ways. Thus there are several possibilities to generalize the square-free concept to graphs. Following Alon, Grytczuk, Haluszczak, Riordan and Bresar, Klavzar we study several so called square-free graph parameters, and answer some questions they posed.

The main result is that the class of k-trees has bounded square-free vertex coloring parameter. Thus we can color the vertices of a k-tree using O(c^k) colors if c>6 such that the color sequence on any path is square-free. It is conjectured that a similar phenomenon holds for planar graphs, so a finite number of colors are enough.

We support this conjecture by showing that this number is at most 12 for outerplanar graphs. On the other hand we prove that some outerplanar graphs require at least 7 colors. Using this latter we construct planar graphs, for which at least 10 colors are necessary. We conclude with some new problems.