On the Facial Thue Choice Index via Entropy Compression

A sequence is nonrepetitive if it contains no identical consecutive subsequences. An edge coloring of a path is nonrepetitive if the sequence of colors of its consecutive edges is nonrepetitive. By the celebrated construction of Thue, it is possible to generate nonrepetitive edge colorings for arbitrarily long paths using only three colors. A recent generalization of this concept implies that we may obtain such colorings even if we are forced to choose edge colors from any sequence of lists of size 4 (while sufficiency of lists of size 3 remains an open problem). As an extension of these basic ideas, Havet, Jendrol', Sotak, and Skrabul'akova proved that for each plane graph, eight colors are sufficient to provide an edge coloring so that every facial path is nonrepetitively colored. In this article, we prove that the same is possible from lists, provided that these have size at least 12. We thus improve the previous bound of 291 (proved by means of the Lovasz Local Lemma). Our approach is based on the Moser-Tardos entropy-compression method and its recent extensions by Grytczuk, Kozik, and Micek, and by Dujmovic, Joret, Kozik, and Wood. (C) 2013 Wiley Periodicals, Inc.