论文部分内容阅读
对于图G，称I(G)={(v，e)∈V(G)×E(G)｜v与e相关联}为G的关联集，说G的两个关联(v，e)和(w，f)是相邻的，当且仅当下列三种情况之一成立：
(1)v=w；(2)e=f；(3)vw=e或vw=f.
图G的一个关联着色是从关联集I(G)到颜色集C的一个影射π，使得I(G)中任何两个相邻的元素都有不同的像。若π：I(G)→C是G的关联着色，且|C|=k，k是一个正整数，则称G是k-可关联着色的。映射π是图G的一个关联着色，使得G是k-可关联着色的最小的k埴称为G的关联色数。
本文主要研究了图的关联色数。第二章确定了两类平面图(花图和棱柱)的关联色数：花图的关联色数等于其最大度加1；对于棱柱Qn(n≥3)，当n≡0(mod5)时，棱柱的关联色数等于其最大度加1，当是其它情况时，棱柱的关联色数等于其最大度加2。第三章首先给出了图与其Mycielski图关联色数的关系：对于任意n阶图G，如果它的关联色数等于其最大度加1，那么当它的最大度的2倍不等于n时，M(G)的关联色数等于△(M(G))+1，当它的最大度的2倍等于n时，M(G)的关联色数小于等于△(M(G))+2；其次还研究了树，最大度△≥5的Halin图，完全二部图的Mycielski图的关联色数：设T为最大度△≥3的树，则M(T)的关联色数等于△(M(T))+1；G为最大度△≥5的Halin图，则M(G)的关联色数等于△(M(G))+1；对于完全二部图Km、n(m，n≥2)，则M(Km，n)的关联色数的关联色数等于△(M(Km,n))+2。