两类图的邻点强可区别E-全染色

2016-10-21顾忠栋强会英魏邦魁

唐山师范学院学报 2016年5期

关键词：定义

顾忠栋，强会英，魏邦魁

（兰州交通大学数理与软件工程学院，甘肃兰州 730070）

两类图的邻点强可区别E-全染色

顾忠栋，强会英，魏邦魁

（兰州交通大学数理与软件工程学院，甘肃兰州 730070）

对简单图G（V，E），存在一个正整数k，使得映射｝，如果∀uv∈E（G），有f（u）≠f（v），f（u）≠f（uv）且C（u）≠C（v），其中C（u）=｛f（u）｝∪｛f（uv），f（v）|uv∈E（G ），v∈V（G）｝，则称f是图G的邻点强可区别E-全染色，且称最小的数k为图G的邻点强可区别E-全色数。本文在此基础上应用构造染色法研究了三正则图R（V，E）、强失积图Pm⊗Pn的邻点强可区别E-全染色，并得出了其邻点强可区别E-全色数。

三正则图；积图；邻点强可区别E-全染色；邻点强可区别E-全色数

1　引言

图的染色理论［1］作为离散数学的一个重要的组成部分，因此受到了国际数学界与工程界越来越广泛的重视。2007年张忠辅教授提出了邻点强可区别全染色［2］的概念。2010年程辉等在邻点强可区别的基础上提出了邻点强可区别EI-全染色［3］和邻点强可区别VI-全染色［4］的概念，本文在此基础上得到了两类图的邻点强可区别E-全染色。下面给出相关的定义。