Repetition-free vertex colorings of grid graphs
Alex Toole · CSUN ScholarWorks (California State University, Northridge) · 2014
A repetition-free coloring of a graph is a coloring of its vertices such that there are no paths for which the color pattern on the first half is repeated on the second half. The Thue chromatic number of a graph is the minimum number of colors required for a repetition-free coloring of the graph. This thesis briefly surveys the history of repetition-free vertex coloring and investigates bounds on the Thue chromatic numbers for a specific class of graphs, the grid graphs. Our focus is on grid graphs which admit repetition-free colorings with 5 colors or less. We include an algorithm which verifies the repetition-free property of a graph coloring. For those colorings such that the number of colors used is more than the average vertex degree less one squared, the algorithm has a running-time in the average case approximately quadratic in the number of vertices of the graph.