完全二部图K6,n当n较小时的点可区别IE-全染色

【摘要】设G是简单图，图G的一个k驳憧汕别IE踩染色（简记为k睼DIET染色），f是指一个从V(G)∪E(G)到{1，2，…，k}的映射，且满足:衭v∈E(G)，有f(u)≠f(v)；衭，v∈V(G)，u≠v，有C(u)≠C(v)，其中C(u)={f(u)}∪{f(uv)|uv∈E(G)}.数min{k|G有一个k睼DIET染色}称为图G的点可区别IE踩色数，记为χievt(G).本文给出了完全二部图K6,n(7≤n≤243)的点可区别IE踩色数.

【关键词】图；点可区别IE踩染色；点可区别IE踩色数；完全二部图

在文献［1，2］中，点可区别正常全染色已被研究过，本文将讨论一种非正常的点可区别全染色.图G的一个全染色叫做图G的正常全染色，如果以下三个条件被满足，条件(v):相邻的两个顶点不能染相同的颜色;条件(e):相邻的两条边不能染相同的颜色;条件(i):任意的点和与之关联的边不能染相同的颜色.如果图G的全染色只满足条件(v)，这样的全染色称为图G的IE踩染色.如果f是图G的使用了k中颜色的IE踩染色，且对任意u,v∈V(G)，u≠v，有C(u)≠C(v)，那么f称为图G的k驳憧汕别IE踩染色，或k睼DIET染色.数min{k|G有一个k睼DIET染色}称为图G的点可区别IE踩色数，记为χievt(G).

对图G，令ni表示度为i的顶点个数，δ≤i≤Δ.设

【参考文献】

［1］陈祥恩.n卜教宓牡憧汕别全染色的渐进性态［J］.西北师范大学学报(自然科学版)，2005，41(5):1-3.

［2］Zhang Zhongfu，QIU Pengxiang，XU Baogen，et al.verter瞕istinguishing total colorings of graphs［J］.Ars Combinatoria 2008，87:33-45.

［3］何文玉，陈祥恩.完全二部图k5,n的点可区别IE踩染色［J］.山东大学学报(理学版)，2009，44(2):91-96.