一类Mycielski图的点可区别均匀无圈边染色.pdfVIP

第33卷总第87期 西 北 民族 大 学 学 报 (自然科学版) Vol_33．NO．3 20l2年 9月 Journalof Northwest University for Nationalities(NaturalScience SeD，2012 一 类Mycielski图的点可区别均匀无圈边染色 薛国梁，田双亮，王晓琦，孙向涛 (西北民族大学 数学与计算机科学学院，甘肃 兰州 730030) [摘 要】设 是简单图G 的k一点可区别边染色，E 表示染颜色 的边所构成的集合，其中f=1,2，…，k．若 对任意f，J=1,2，…，k，G中没有双色圈且 I—lE．11≤1，则称()_是G的尼一点可区别均匀无圈边染色．最小的 10 。 I J ll k值称为G的点可区别均匀无圈边色数．文章讨论了最大度为 2的图Mycielski图的点可区别均匀无圈边染色，并得 到了相应的色数值． [关键词] Mycie1ski图；点可区别均匀无圈边染色；点可区别均匀无圈边色数 [中图分类号]0213．2：0141．2 【文献标识码】A [文章编号】1009—2102(2012)030010-04 0 引 言 Alon等人最早提出了图G的无圈边染色…概念，随后许多学者对无圈边染色和有限制条件的无 圈边染色做了研究．文献 [2～5]分别研究了平面图的无圈边染色、均匀边染色、正则图的点可区别正 常边染色以及图的邻点可区别无圈边染色．文献 [6～8]对Mycielski图的有限制条件的全染色做了 研究．本文将研究最大度为2的图Mycielski图的点可区别均匀无圈边染色．文中所考虑的图G都是 有限无向简单图，用 (G)，E(G)分别表示G的顶点集和边集，用A(G)表示G的最大度，未加说 明的术语及符号可参见文献 [1]和 [9]． 定义 1．11【_习 图G的一个正常k一边染色 ()．称为k一均匀无圈边染色，如果G中没有双色圈，且 IlEJ—IE川 1，其中Ei与 ，分别表示染颜色 与J的边构成的集合，且称最小的k值为G的均匀无 l’ 。 I lI 圈边色数． 定义 1．2 设 为图G 的一个正常k一边染色， ()为顶点U在 ()_下的色集，记为 (“)={cr(uv)lUV∈ (G))．若对G的任意两个不同的顶点 “和v，有 u)≠ (v)，则称 为 G的k一点可区别边染色，且称最小的k值为G的点可区别边色数． 若G的一个正常k一边染色 ()_同时满足定义 1．1与定义 1．2的条件，则称 (，-为G的点可区别均匀 无圈边染色，所用最少颜色数称为G的点可区别均匀无圈边色数，记为S／f(．a)． vea 显然， (G) △(G)． 一 定义 1．3。 具有顶点集{Xo，Xl，…，Xn一)的图G的Mycielski图 (G)是指具有顶点集 {Xo，Xl，…，Xn一)U{Yo，，一。，一i)U{z)与边集E(G)U l『 ，eE(G)，i，J=O，1，…，一1) U{2)，fI=O，1，…，，2—1)的图，其中{Xo，Xl，…，X川)，{YoY,，…，一1}与{z)两两不相交． 在后面的讨论中，将用到以下引理： [收稿 日期]2012_08—2O [基金项目】中央高校基本科研业务费专项资金项目(ZYZ2012089)；国家民委科研资助项 目(10XB01) [作者简介】薛国梁 (1980——)，男，陕西韩城人，主要从事图论及组合优化方面的研究． 一 1O一 万方数据 引理1． 。 对任意一个图G，都有△(G) ’(G) △(G)+2 1 主要结果及证明 图的边染色或加有限制条件的边染色实际是对图G的边集E(G)的一一个分类(互，Ez，…， )，其 中每个E均为G的匹配．在本文中，我们将用寻找匹配的方法划分图的边集，构造图的点可区别均 匀无 边染色． 定理2．1 设 为n阶 ，其中n 5，则