关于图的邻点可区别全染色的一些结果

论文摘要

本文给出了一个图的k重Mycielski图,两个图的直积以及冠图的定义,得到了简单图G的k重Mycielski图Mk（G）的邻点可区别全色数χat（Mk（G））与χat（G）之间的一个关系.对于两个简单图G、H的直积图G×H,讨论并得到了其邻点可区别全色数与χat（G）以及H的邻点可区别正常边色数之间的关系.利用这两个关系可以直接得到偶阶完全图的k重Mycielski图以及直积图Sn×Pm、Wn×Pm、Fn×Pm、Sn×Sm、Wn×Wm、Fn×Fm的邻点可区别全色数的具体值.另外,通过具体构造染色的方法讨论并给出了圈、星、扇、轮的k重Mycielski图,直积图Sn×Cm、Wn×Cm、Fn×Cm、Kn×Km（其中m、n均为偶数）、Kt×Kt（t为奇数）,以及冠图（m,n≥5）、（m,n≥5）的邻点可区别全色数.

论文目录

• 摘要
• Abstract
• 前言
• 1 预备知识
• 2 k重Mycielski图的邻点可区别全染色
• 3 图的直积的邻点可区别全染色
• 4 冠图的邻点可区别全染色
• 参考文献
• 致谢