关于图Cn·Cm,Cn·Fm,Cn·Wm的邻强边着色

摘要

设图G(V,E)为简单图,其点数不小于3.图G(V,E)的k-邻强边染色是指映射f:E(G)→{1,2,…,k},使f为正常边着色,且( ) u,v ∈ V(G),当uv ∈ E(G)时,有C(u)≠C(v),其中C(u)={f(uv)Iuv∈E(G)}.记Xas(G)=min{k|G有k-邻强边着色法}.称Xas(G)为G的邻强边色数.本文构造了三类图Cn·Cm,Cn·Fm,Cn·Wm,通过对图的具体着色得到其邻强边色数分别为4,m+1,m+1.