On Square-Free Edge Colorings of Graphs

Abstract

An edge coloring of a graph is called $square-free$ if the sequence of colors on certain walks is not a square, that is not of the form $x_1,\dots ,x_m,x_1,\dots ,x_m$ for any $m\in \mathbb{N}$. Recently, various classes of walks have been suggested to be considered in the above definition. We construct graphs, for which the minimum number of colors needed for a square-free coloring is different if the considered set of walks vary, solving a problem posed by Brešar and Klavžar. We also prove the following: if an edge coloring of $G$ is not square-free (even in the most general sense), then the length of the shortest square walk is at most $8|E(G){|}^2$. Hence, the necessary number of colors for a square-free coloring is algorithmically computable.