Pattern avoidance on graphs (Q878624)

The paper studies colorings of graphs avoiding certain patterns on paths. Let \(X\) be a set of variables and let \(p=x_1x_2\dots x_r\) (with \(x_i\in X\)) be a pattern, i.e. any sequence of the variables with repetition allowed. A finite sequence \(s\) is said to match the pattern \(p\), if \(s\) can be divided into non-empty blocks \(s=B_1B_2\dots B_r\), such that \(x_i=x_j\) implies \(B_i=B_j\) for all \(1\leq i,j\leq r\). A coloring of vertices (or edges) of a graph \(G\) is said to be \(p\)-free if no path in \(G\) matches the pattern \(p\). The pattern chromatic number \(\pi_p(G)\) is the minimum number of colors used in a \(p\)-free coloring of \(G\). Extending results of \textit{N. Alon, J. Grytczuk, M. Hałuszczak}, and \textit{O. Riordan} [Random Struct. Algorithms 21, 336--346 (2002; Zbl 1018.05032)], the paper shows that if each variable occurs at least \(m\geq 2\) times in a pattern \(p\), then \(\pi_p(G) \leq c \Delta^{m/(m-1)}\), where \(c\) is an absolute constant and \(\Delta\) is the maximum degree of the graph \(G\). The proof is probabilistic and depends on the Lovász Local Lemma. For certain graph classes stronger results are achieved by providing explicit \(p\)-free colorings. In particular, for some patterns \(p\), the pattern chromatic number has an absolute upper bound for all trees.