若干图的广义字典积的全染色

作者：田双亮; 孙向涛

来源：山西大学学报(自然科学版), 2013, (02): 152-155.

DOI：10.13451/j.cnki.shanxi.univ(nat.sci.).2013.02.028

• 广义字典积
• 全染色
• 全色数 generalized lexicographic product
• total coloring
• total chromatic number

设G是具有顶点集{t0,t1,…,tn-1}的轮,或扇,或星,其中t0为最大度点,且n≥5.G[hn]是图G与顶点不相交图序列hn=(Hi)i∈{0,1,…,n-1}的广义字典积,其中每一个Hi为m阶简单图.论文得到了以下结果:(1)若H0为完全图的补图,则G[hn]的全色数为(n-1)m+1;(2)若H0为完全图,则G[hn]的全色数为mn;(3)若H0为二部图,则G[hn]的全色数为Δ(H0)+(n-1)m+1,其中Δ(H0)表示图H0的最大度;(4)若H0为m阶圈,m≥3,则G[hn]的全色数为(n-1)m+3.

• 单位
  西北民族大学