论文部分内容阅读
本文研究了图的广义字典积的邻点可区别边染色与邻点可区别全染色,以及图的半强积的点可区别边染色与邻点可区别全染色,并利用图分解技术与构造染色的方法给出了相应染色数的可达上界.在此基础上,确定了一些特殊图的广义字典积与半强积的相应染色数的精确值.主要结果包括四个部分：第 ,得到了图G与图序列hp=(Hi)i∈{0,1...,n-1}的广义字典积G[hn]的邻点可区别边色数的两个上界：(1)若G存在χ’as(G)-邻点可区别边染色,使得该染色中某一色类的边将G的所有最大度点全部饱和,则χ’as(G[hn])≤mχ’as(G)+χ’(H0)+1,其中χ’(H0)=max{χ’(Hi)|ti∈V△(G)},且V△(G)表示G的最大度点构成的集合.(2)χ’as(G[hn])≤mχ’as(G)+χ’as(H0),其中χ’as(H0)=max{χ’as(Hi)|ti∈V△(G)}.验证了以上两个上界是可达的.并对满足χ’as(G)=△(G)的图G,给出了当H0分别为完全图和树时广义字典积G[hn]的邻点可区别边色数的精确值.对满足χ’as(G)=△(G)和χ’as(H)=△(H)的图G与H的两个字典积G[H]与H[G],确定了它们的邻点可区别边色数.另外,对最大度相等且邻点可区别边色数为其最大度的p个连通图的字典积Gp[Gp-1[…G2[G1]…]],得到了它的邻点可区别边色数,并证明该色数与G1,G2,…,G。的顺序无关.第二,得到了n≥6阶轮或扇或星与m≥2阶连通图序列hn=(Hi)ie{0,1,...,n-1}的广义字典积G[hn]的邻点可区别全色数的一个可达上界：χ’at(G[hi])≤m(m-1)+min{χr(H0)+1,χat,(H0)},其中H0与G的最大度点t0对应.并利用该结果给出了当H0分别为树、圈、路、完全图、正则二部图时G[hn]的邻点可区别全色数的精确值.第三,得到了阶至少为3的两个简单联通图G与H的半强积G·H的点可区别边色数的一个可达上界：χ’vd(G·H)≤△(H)χ’vd(G)+χ’vd(H).在此基础上,对于满足χ’vd(G)=△(G)的图G,得到了G与满足χ’vd(H)=△(H)的图H的半强积,以及G与完全图的半强积的点可区别边色数的精确值.另外,对最大度相等且点可区别边色数为其最大度的p个连通图的半强积Gp·(Gp-1·(…·(G2·G1)…)),确定了它的点可区别边色数,并证明该色数与G,,G2,…,Gp的顺序无关.第四,得到了阶至少为2的两个简单连通图G与H的半强积G·H的邻点可区别全色数的一个可达上界：χol,(G·H)≤△(H)χ’(G)+χal(H).并利用该上界给出了第一类图与非平凡树、圈的半强积,两个正则二部图的半强积,以及两个非平凡树的半强积的邻点可区别全色数的精确值.另外,得到了p个非平凡树的半强积Tp-1,·(Tp-2·(…·(T1·T0)…))的邻点可区别全色数.