论文部分内容阅读
图G的Smarandachely邻点可区别V-全染色 f是从V(G)?E(G)到{1,2,...,k}的映射,满足:⑴相邻边的像不同;⑵顶点的像与其关联边的像不相同;⑶图G的任意相邻两点的像集合互不包含.将所用最少的色数称为该图G的Smarandachely邻点可区别V-全色数.其中每一点的像集合为该点与其关联边的像所组成的集合. 本文主要运用穷举法和构造函数法研究了路、圈、星、扇、轮图构成的冠图,以及这些简单图的倍图,Mycielski图,三种积图(直积图、笛卡尔积图、半强矢积图)及广义Mycielski图的Smarandachely邻点可区别V-全染色,并得到了这些图的Smarandachely邻点可区别V-全色数,验证了这些图对于Smarandachely邻点可区别V-全染色猜想成立. 本文共分为六个部分: 第一部分主要介绍了图染色的相关概念和基本理论. 第二部分研究了若干冠图的Smarandachely邻点可区别V-全染色,并得到了其Smarandachely邻点可区别V-全色数,验证了Smarandachely邻点可区别V-全染色猜想. 第三部分研究了若干倍图的Smarandachely邻点可区别V-全染色,并得到了其Smarandachely邻点可区别V-全色数,验证了Smarandachely邻点可区别V-全染色猜想. 第四部分研究了若干Mycielski图的Smarandachely邻点可区别V-全染色,并得到了其Smarandachely邻点可区别V-全色数,验证了Smarandachely邻点可区别V-全染色猜想. 第五部分研究了三种积图(直积图、笛卡尔积图、半强矢积图)的Smarandachely邻点可区别 V-全染色,并得到了其 Smarandachely邻点可区别 V-全色数,验证了Smarandachely邻点可区别V-全染色猜想. 第六部分研究了若干广义Mycielski图的Smarandachely邻点可区别V-全染色,并得到了其Smarandachely邻点可区别V-全色数,验证了Smarandachely邻点可区别V-全染色猜想.