Pattern avoidance on graphs

In this paper we consider colorings of graphs avoiding certain patterns on paths. Let XX be a set of variables   and let p=x1x2…xr,xi∈Xp=x1x2…xr,xi∈X, be a pattern  , that is, any sequence of variables. A finite sequence ss is said to match   a pattern pp if ss may be divided into non-empty blocks s=B1B2…Brs=B1B2…Br, such that xi=xjxi=xj implies Bi=BjBi=Bj, for all i,j=1,2,…,ri,j=1,2,…,r. A coloring of vertices (or edges) of a graph GG is said to be pp-free   if no path in GG matches a pattern pp. The pattern chromatic number  πp(G)πp(G) is the minimum number of colors used in a pp-free coloring of GG.Extending the result of Alon et al. [Non-repetitive colorings of graphs, Random Struct. Alg. 21 (2002) 336–346] we prove that if each variable occurs in a pattern pp at least m⩾2m⩾2 times then πp(G)⩽cΔm/(m-1)πp(G)⩽cΔm/(m-1), where cc is an absolute constant. The proof is probabilistic and uses the Lovász Local Lemma. We also provide some explicit pp-free colorings giving stronger estimates for some simple classes of graphs. In particular, for some patterns pp we show that πp(T)πp(T) is absolutely bounded by a constant depending only on pp, for all trees TT.