Avoiding large squares in trees and planar graphs

Abstract

The Thue number $\pi (G)$ of a graph $G$ is the minimum number of colors needed to color $G$ without creating a square on a path of $G$. For a graph class $C$, $\pi (C)$ is the supremum of $\pi (G)$ over the graphs $G\in C$. The Thue number has been investigated for famous minor-closed classes: $\pi (tree)=4$, $7\le \pi (outerplanar)\le 12$, and $11\le \pi (planar)\le 768$. Following a suggestion of Grytczuk, we consider the generalized parameters ${\pi }_k(C)$ such that only squares of period at least $k$ must be avoided. Thus, $\pi (C)={\pi }_1(C)$. We show that ${\pi }_5(tree)=2$, ${\pi }_2(tree)=3$, and ${\pi }_k(planar)\ge 11$ for every fixed $k$.