论文部分内容阅读
图G的关联着色是指从关联集I(G)到颜色集合C的一个映射σ,使得G中任何两个相邻关联具有不同的象.若σ:I(G)→C是G的一个关联着色,且|C|=k,则称σ是G的k-关联着色,且称G是k-可关联着色的,其中k是一个正整数.使得G是k-可关联着色的最小的数值k称为G的关联色数,记为xi(G),即xi(G)=min{|C||σ:I(G)→C是G的关联着色}. 本文主要对平面图和联图的关联着色进行了研究.首先,通过放电法,得到了对任意不含三角形的平面图G,当△(G)≥7时,其关联色数不超过△(G)+3;并证明了对围长g≥5且不含相邻的5-面与k-面的平面图G,其中k≤7,若△(G)≥6,则其关联色数不超过△(G)+2.其次,通过分析两个图的联图的结构,得到了图G与H的联图G∨H的关联色数的一个上界max{|V(G)|,|V(H)|}+max{xi(G),xi(H)}+2,并讨论了联图Pm∨Pn、Pm∨Cn和Cm∨Cn的关联色数.得到了 (i)对路Pm与Pn的联图Pm∨Pn,当m≥3时,Pm∨P2的关联色数为m+2;Pm∨P3的关联色数为m+3;当m≥n≥4时,Pm∨Pn的关联色数为m+4. (ii)对路Pm与圈Pn的联图Pm∨ Cn,当m≥3时,Pm∨ C3的关联色数为m+3;当m≥4,n≥4时,Pm∨ Cn的关联色数为max{m,n}+4. (iii)对圈Cm与Cn的联图Cm∨Cn,当3≤n≤m≤4时,Cm∨Cn的关联色数为m+n;当n≥5时,Cn∨ C3的关联色数为n+3; Cn∨C4的关联色数为n+4;并且,Cn∨Cn的关联色数为n+4或n+5.进一步,若n≡0(mod4),则Cn∨Cn的关联色数为n+4. 最后,讨论一些特殊图类与P2的强积图以及路与路的强积图的关联色数.