论文部分内容阅读
设图G的点集V(G)={v1,v2,…,vn},Vi是点集(i=1,2,…,n),G的膨胀图FG的点集V(FG)=V1UV2U…UVn,且对x∈Vi,y∈Vj,有xy∈E(FG),当且仅当i=j或vivj∈E(G).若对所有的i,满足|Vi|=t,则称其为G的一致膨胀图.证明了树的膨胀图的关联色数是最大度加1,K2,n的一致膨胀图的关联色数为最大度加2.