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