论文部分内容阅读
图G的一个k-无圈边染色是满足任意两种颜色类的导出子图是森林的G的一个k-正常边染色,G的无圈边色数是使G存在无圈边染色最少的颜色数,记为a’(G).G的一个k-孪生边染色σ是指能诱导出正常点染色σ的G的k-正常边染色,其中颜色集合为[k]={0,1,…,k-1},且对每一v∈V(G),有(?)最少的颜色uveE(G)数称为G的孪生边色数,并记为χ1’(G).本文主要研究了有限路的笛卡尔积、直积、半强积与强积的无圈边染色,以及无限路的笛卡尔积、直积、半强积与强积的孪生边染色,并得到了相应染色数.主要内容包括以下两个部分.第一、得到了两个路Pm和Pn的笛卡尔积Pm·Pn、直积Pm^Pn、半强积Pm·Pn与强积Pm(?)Pn的无圈边色数,其中m≥2,n≥2.具体结果如下:1、若n = m = 2,则a’(Pn·Pn)=△(Pm·Pn)+ 1,否则,a’(Pm·Pn)=△(Pm·Pn);2、a’(Pm^Pn)=△(Pm^Pn);3、若n = m = 2,则a’(Pn·Pn)=△(Pm·Pn)+ 1,否则,a’(Pm·Pn)=△(Pm·Pn);4、对n≥m≥2,若n = m = 2,则(Pm(?)Pn)= △(Pm(?)Pn)+ 2,若m = 2且n≥4;则a’(Pm(?)Pn)=△(Pm(>)Pn)+ 1;若m = 2且n=3,或n≥m≥3,则a’(Pm(?)Pn)=△(Pm(?)Pn).第二、得到了两个无限路P。P∞与P∞’的笛卡尔积P∞·P∞’、直积P∞^P∞’、半强积P∞`∞’与强积P∞(?)P∞’孪生边色数,具体结果如下:1、χt’(P∞·P∞’)=△(P∞·P∞’)+1 = 5.2、χt’(P∞^P∞’)=△(P∞^P∞’)+1 = 5.3、χt’(P∞·P∞’)=△(P∞·P∞’)+1 = 7.4、χt’(P∞(?)P∞’)=△(P∞(?)P∞’)+1 = 9.