Square-Free Colorings of Graphs

Abstract

Let $G$ be a graph and let $c$ be a coloring of its edges. If the sequence of colors along a walk of $G$ is of the form $a_1,\dots ,a_n,a_1,\dots ,a_n$, the walk is called a square walk. We say that the coloring $c$ is square-free if any open walk is not a square and call the minimum number of colors needed so that $G$ has a square-free coloring a walk Thue number and denote it by ${\pi }_w(G)$. This concept is a variation of the Thue number introduced by Alon, Grytczuk, Hatuzczak, and Riordan in [2].

Using the walk Thue number, several results of [1] are extended. The Thue number of some complete graphs is extended to Hamming graphs. This result (for the case of hypercubes) is used to show that if a graph $G$ on $n$ vertices and $m$ edges is the subdivision graph of some graph, then ${\pi }_w(G)\le n–\frac{m}{2}$. Graph products are also considered. An inequality for the Thue number of the Cartesian product of trees is extended to arbitrary graphs and upper bounds for the (walk) Thue number of the direct and the strong products are also given. Using the latter results, the (walk) Thue number of complete multipartite graphs is bounded, which in turn gives a bound for arbitrary graphs in general and for perfect graphs in particular.