A word w =uu is called a long square if u is of length at least 3; a word w is called long-square-free if w contains no sub-word that is a long square. If there exists a k-coloring of the vertices of a graph G such that, for any path P in G, the word generated by the coloring of P is long-square-free, then G is called long-repetition-free} k-colorable. We show that every rooted tree of radius r <= 7 is long-repetition-free 2-colorable. We also show that there exists a class of trees which are not long-repetition-free 2-colorable.
David Milan, Associate Professor of Mathematics, The University of Texas at Tyler
Antonides, Joseph; Kiers, Claire; and Yamzon, Nicole
"On the Long-Repetition-Free 2-Colorability of Trees,"
Rose-Hulman Undergraduate Mathematics Journal: Vol. 18
, Article 15.
Available at: http://scholar.rose-hulman.edu/rhumj/vol18/iss1/15