若干Mycielski图邻点可区别Ⅰ-均匀全染色

张 婷＊1， 朱 恩 强， 赵 双 柱， 杜 佳

（1.兰州文理学院 师范学院，甘肃 兰州 730000；2.北京大学 信息科学技术学院，北京 100871；3.兰州文理学院 数字媒体学院，甘肃 兰州 730000）

0 引 言

关于均匀染色的概念最早是由Meyer［1］提出的，1994年，Fu［2］提出了均匀全染色概念以及均匀全染色猜想.许多学者围绕图的均匀全染色做了大量研究［3－5］.文献［6-8］研究了一些特殊图的点可区别Ⅰ-全染色和邻点可区别Ⅰ-全染色.文献［9］给出了路、圈、扇、轮、完全图、完全二部图的邻点可区别Ⅰ-均匀全色数，提出邻点可区别Ⅰ－均匀全色数最大不超过2的猜想；文献［10］研究了几类图的均匀邻点可区别Ⅰ-全染色.本文根据图M（Pn）、M（Cn）和 M（Sn）的构造特征，利用函数构造法，研究并确立它们邻点可区别Ⅰ-均匀全色数，并验证其满足猜想.

1 相关定义和引理

定义1［11］对于阶数不小于2的连通图G（V，E），设f是从V（G）∪E（G）到｛1，2，…，k｝的映射，k为自然数，如果f满足

（1）对uv∈E（G），u≠v，有f（u）≠f（v）；

（2）对 uv，uw∈E（G），v≠w，f（uv）≠f（uw）；

（3）对uv∈E（G），u≠v，C（u）≠C（v）则称f为图G的一个邻点可区别的Ⅰ-全染色（简记为k-Ⅰ-AVDTC）.记χiat（G）＝min｛k｜G 的k-Ⅰ-AVDTC｝为图G的邻点可区别Ⅰ-全色数.其中C（u）＝｛f（u）｝∪｛f（uv）｜uv∈E（G）｝称为点u在f下的色集，C（u）在色全集合C＝｛1，2，…，k｝中的补集记为C（v）＝C＼C（u）.

定义2［9］设f 是简单连通图G（V，E）（V（G）≥2）的一个k-Ⅰ-AVDTC，若满足i，j∈｛1，2，…，k｝，i≠j，有 Ti－Tj≤1，则称f为图G的一个k-邻点可区别Ⅰ-均匀全染色（简记为k-Ⅰ-AVDETC），而称（G）＝min｛k｜G 的k-Ⅰ-AVDETC｝为图G的邻点可区别Ⅰ-均匀全色数，其中 Ti＝Vi∪Ei，Vi＝｛v｜v∈V（G），f（v）＝i｝，Ei＝｛e｜e∈E（G），f（e）＝i｝.

定义 3［12］对简单图 G，若V（M（G））＝V（G）∪V′∪｛w｝，E（M（G））＝E（G）∪｛uv′｜u∈V（G），v′∈V′，uv∈E（G）｝∪｛wv′｜v′∈V′｝，其中V′＝｛v′｜v∈V（G）｝，｛w｝∩（V∪V′）＝，称图M（G）是图G的Mycielski图.

猜想1［9］对简单连通图G，有（G）≤Δ（G）＋2.

引理1［9］（G）≥Δ（G），Δ（G）表示图G的最大度.

引理2［9］对 V（G）≥2的连通图G，若有最大度点相邻.

文中未加说明的符号或术语可参见文献［13］.

2 主要结论

定理1 设Pn表示阶为n（n≥3）的路，则有

证明 以下分3种情形证明本定理.

情形1 当n＝3时，Δ（M（P3））＝4，由引理1知（G）≥Δ（G），为证定理为真，只需给出M（P3）的一个4-Ⅰ-AVDETC.为此，构造映射f：V（M（P3））∪E（M（P3））→｛1，2，3，4｝，f（v1）＝f（v′1）＝f（v1v2）＝f（v3v′2）＝1；……