论文部分内容阅读
本文通过归纳定义了图的三类染色—无圈染色，邻点可区别的染色和点可区别的染色.应用Lovász局部引理的赋权形式，讨论并得到了任一最大度△≥4的图G，其邻点可区别的无圈边色数至多为16△2.应用Lovász局部引理的一般形式，讨论并得到了任一最大度△≥322ln5，最小度δ≥32√△ln△的图G，其邻点可区别的全色数至多为2△+1+2√△ln△；进一步，若全色数xt(G)≤△+2，则其邻点可区别的全色数至多为△+2+2√△ln△.然后，通过具体构造染色的方法讨论并给出了路、圈、完全图、星、扇、轮的Mycielski图，路与圈的联图Pm()Sn的点可区别的全色数.