Nonrepetitive colorings of graphs of bounded tree-width (Q941387): Difference between revisions

A block of a sequence is a subsequence consisting of consecutive terms of the sequence. A sequence of the form \(s_1s_2 \cdots s_ms_1s_2 \cdots s_m\) is called a repetition. A sequence is called nonrepetitive if none of its blocks is a repetition. For any set of colors \(\mathbf C\), a coloring of a graph \(G\) is a function \(c: V(G) \rightarrow {\mathbf C}\). Let \(B_m\) be the collection of all repetitions of length at most \(2m\) over \(\mathbf C\). We say that a coloring of \(G\) is \(B_m\)-free if for every path \(v_1v_2 \cdots v_k\) we have \(c(v_1)c(v_2) \cdots c(v_k) \notin B_m\). Thus a \(B_1\)-free coloring is just a proper vertex-coloring and a \(B_2\)-free coloring has been studied under the name star coloring. An outstanding open problem posed by Alon et al. asks if there is a constant \(k\) such that every planar graph has a nonrepetitive \(k\)-coloring. It is proved in this paper that every outerplanar graph has a nonrepetitive 12-coloring and a graph with tree-width at most \(t\) has a nonrepetitive \(4^t\)-coloring. The authors also construct 2-degenerate graphs of girth \(2m+2\) which have \(B_m\)-free 5-colorings but no \(B_{m+1}\)-free \(k\)-colorings.