路的积的无圈边染色与孪生边染色

发布时间：2018-03-12 11:32

  本文选题：有限路　切入点：无限路　出处：《西北民族大学》2017年硕士论文　论文类型：学位论文

【摘要】：图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.
[Abstract]:A k-acyclic edge coloring of a graph G is an derived subgraph satisfying any two color classes. The number of acyclic edges of a k-normal edge coloring G of a forest is the least number of colors in which G has an acyclic edge coloring. A k- twinning edge coloring 蟽 is a k- normal edge coloring of G which can induce normal point coloring 蟽, where the set of colors is [k] = {0 ~ 1, 鈥，

本文编号：1601372