Pattern avoidance on graphs

Abstract: In this paper we consider colorings of graphs avoiding certain patterns on paths. Let be a set of variables and let , be a pattern, that is, any sequence of variables. A finite sequence is said to match a pattern if may be divided into non-empty blocks , such that implies , for all . A coloring of vertices (or edges) of a graph is said to be -free if no path in matches a pattern . The pattern chromatic number is the minimum number of colors used in a -free coloring of . 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 at least times then , where is an absolute constant. The proof is probabilistic and uses the Lovász Local Lemma. We also provide some explicit -free colorings giving stronger estimates for some simple classes of graphs. In particular, for some patterns we show that is absolutely bounded by a constant depending only on , for all trees . [Copyright &y& Elsevier]