圈的无重复分数染色

朱绪鼎， 钟亚玲

(浙江师范大学 数理与信息工程学院,浙江 金华 321004)

0 引 言

如果一个偶长度的序列x1x2…x2l的前一半和后一半是一样的,即对任意的1≤i≤l,xi=xi+l,那么就称该序列为一个重复.如果一个序列不含有重复的子序列,那么就称该序列为一个无重复的序列.1906年，Thue[1]证明了仅用3个符号可以写出一个无限长的无重复序列.Thue的这个结果在数学的很多分支中有重要的影响,它催生了一个新的学科：符号动力学.Thue定理及其推广在数学和计算机科学的不同领域中有许多重要的应用.

2002年，Alon等[2]将无重复序列的概念和图的染色结合起来,提出了图的无重复染色的概念.图G的一个顶点染色c是无重复的是指图G中的任何一条简单路v1v2…v2l的颜色序列c(v1)c(v2)…c(v2l)不是一个重复.称一个无重复染色所需要的最少颜色数为图G的Thue染色数，记为π(G),即

π(G)=min{n:图G存在一个无重复的n-染色}.

根据π(G) 的定义,Thue的结果等价于π(P∞)=3.

图的无重复染色数在文献[2-6]中已有大量的研究,得到了许多类图的无重复染色数的上下界.特别是在文献[4]中,Currie确定了所有圈图的无重复染色数.

定理1[4]设Cn是顶点数n≥3的圈图.若n=5,7,9,10,14,17,则π(Cn)=4;否则π(Cn)=3.

下面给出图G的无重复分数染色的定义.

根据πf(G)的定义,对任意的图G,πf(G)≤π(G).一个很自然的问题是:哪些图G满足πf(G)=π(G)?如果πf(G)≠π(G),那么π(G)-πf(G)的差值有多大?笔者已另文(待发表)证明了,若图G是一条路或者是一棵没有2度点的树,则πf(G)=π(G)；同时还构造了一个树图T,它的无重复分数染色数是3.5,而它的无重复染色数是 4；对于圈图的无重复分数染色数,得出除……