若干图类的Smarandachely邻点全染色

论文摘要

对于简单图G,f是图G的一个正常全染色（即：相邻顶点、相邻边以及关联元素都染不同色的一个全染色）.进一步,如果相邻两点的色集合互不包含,则称该染色法f为Smarandachely邻点全染色,把所用最少颜色数称为该图G的Smarandachely邻点全染色数.其中某一点的色集合为点及其关联边所染的颜色构成的集合.近年来,穷举法、组合分析法以及结构拼凑法成为了研究图染色的主要方法.所谓穷举法就是在已知图的某种染色的色数的下界（上界）之后,在这个图的同构类里找出一个图施行这种染色,通过给每个元素染色来说明其色数是存在的；组合分析法就是通过分析图的结构,运用组合学的来研究图染色的方法；结构拼凑法是从图的结构出发,对图的局部进行着色,然后通过拼凑来实现整个图的染色.本文应用上述三种方法,研究了路、圈、星、扇、轮、完全图、联图、四种积图（直积图、卡氏积图、强积图、半强积图）和若干3-正则图的Smarandachely邻点全染色,并得到了这些图类的Smarandachely邻点全色数.文章分为以下四部分：第一章介绍了图的一些基本概念及其猜想.第二章给出了若干简单图以及联图的Smarandachely邻点全染色结果.第三章主要研究了四种积图（直积图、卡氏积图、强积图、半强积图）的Smarandachely邻点全染色,得到了其Smarandachely邻点全染色,进一步验证了这些图对Smarandachely邻点全染色猜想成立.第四章构造了若干类3-正则图,并给出了若干3-正则图的Smarandachely邻点全染色,得到了其色数,进一步验证了3-正则图的Smarandachely邻点全染色猜想成立.

论文目录

• 摘要
• Abstract
• 引言
• 1 基本概念及相关猜想
• 2 若干简单图及联图的Smarandachely邻点全染色
• 2.1 一些简单图的Smarandachely邻点全染色
• 2.2 一些联图的Smarandachely邻点全染色
• 3 四种积图的Smarandachely邻点全染色
• 3.1 四种积图的定义
• 3.2 若干直积图的Smarandachely邻点全染色
• 3.3 若干笛卡尔积图的Smarandachely邻点全染色
• 3.4 若干强积图的Smarandachely邻点全染色
• 3.5 若干半强积图的Smarandachely邻点全染色
• 4 若干3-正则图的Smarandachely邻点全色数
• 4.1 三类3-正则Halin图的Smarandachely邻点全染色
• 4.2 两类3-正则图的Smarandachely邻点全染色
• 4.3 一类3-正则重圈图的Smarandachely邻点全染色
• 结论
• 致谢
• 参考文献
• 攻读学位期间的研究成果