Square-free Walks on Labelled Graphs

Abstract

A finite or infinite word is called a $G$-word for a labelled graph $G$ on the vertex set $A_n=\{0,1,...,n-1\}$ if $w=i_1{i}_2...i_k\in A_n^{\ast }$, where each factor $i_j{i}_{j+1}$ is an edge of $E$, i.e, $w$ represents a walk in $G$. We show that there exists a square-free infinite $G$-word if and only if $G$ has no subgraph isomorphic to one of the cycles $C_3,C_4,C_5$, the path $P_5$ or the claw $K_{1,3}$. The colour number $\gamma (G)$ of a graph $G=(A_n,E)$ is the smallest integer $k$, if it exists, for which there exists a mapping $\varphi :A_n\to A_k$ such that $\varphi (w)$ is square-free for an infinite $G$-word $w$. We show that $\gamma (G)=3$ for $G=C_3,C_5,P_5$, but $\gamma (G)=4$ for $G=C_4,K_{1,3}$. In particular, $\gamma (G)\le 4$ for all graphs that have at least five vertices.