幂图的全色数.pdfVIP

第 29卷第 2期 徐州师范大学学报 (自然科学版) Vo1．29，No．2 2011年 6月 JournalofXuzhouNormalUniversity(NaturalScienceEdition) Jun．，2011 幂图的全色数 孟献青 (山西大同大学 数学与计算机科学学院，山西 大同037009) 摘要：根据幂图的结构性质，利用穷染、替换的方法，研究了幂图P 的全色数，并给出了一种染色方案 关键词 ：路 ；幂 图；全染色 ；全色数 中图分类号 ：O157 文献标识码 ：A 文章编号：1007—6573(2011)02—0022—02 Thetotalchromaticnumberofpowergraph MengXianqing (SchoolofMathematics ComputerScience。ShanxiDatongUniversity，Datong037009，Shanxi，China) Abstract：Accordingtothepropertiesofpowergraph，byusingcoloronebyoneandreplacement，thetotalcoloring chromaticnumberofpowergraphP isstudied，andacoloringmethodisgiven． Keywords：path；powergraph；totalcoloring；totalchromaticnumber 则称 为G 的k幂图． 1 基本知识 引理 1_l4j 设 C 是 ≥3的圈，当 三0(rood 本文讨论 的都是有 限无 向简单 图．用 V(G)， 3)时 ，有XT(C)一3． (G)和△(G)分别表示 图G的顶点集、边集和最大 文献[2]研究了幂图的邻点可区别全色数，文献 度．记 Q(G)一 (G)UE(G)，V==={Id()：i)．文 E5]研究了联图CVK 的全色数．通过研究两种色 中未说明的术语和记号参阅文献[1—3]．为叙述方 数之间的关系 ，本文给出幂图P 的全色数． 便 ，下面给出相关的定义和结论． 2 定理及其证 明 定义 1 设 G是阶数不小于 2的简单连通 图，k是正整数 ，令 厂是从Q(G)到集合 {1，2，…，忌) 定理 1 对于 n(n≥3)阶路的平方图P ，有 的映射 ，若 f3， 一3； i)V “，叫∈E(G)，≠W，有 xT(P：)一 4， n一4； f(uv)≠f(vw)； I5， ≥5． ii)V “∈E(G)，有 证 设路 P一 12… ． 厂()≠f(uv)，厂()≠f(uv)，，(乱)≠厂()， 当 一3时，由引理 1知 ，xT(P；)一xT(C。)一3． 则称 厂为图G 的一个 k正常全染色，简称为 k全 当 一4时 ，令 染色． f(v1732)一．厂( 4)===1， 全染色所用颜色的最少数 目称为图G 的全色