期刊
JOURNAL OF GRAPH THEORY
卷 77, 期 3, 页码 180-189出版社
WILEY
DOI: 10.1002/jgt.21781
关键词
Thue sequence; nonrepetitive list coloring; facial Thue choice index; plane graph
类别
资金
- Polish Ministry of Science and Higher Education
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据