图邻点可区别无圈边染色及几类非正常染色

《图邻点可区别无圈边染色及几类非正常染色》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文M.D.Thesis图的邻点可区别无圈边染色及几类非正常染色TheAdjacentVertexDistinguishingAcyclicEdgeColoringandSomeClassesofImproperColoring王志强WangZhiqiang数学与信息科学学院CollegeofMathematicsandInformationScience目录独创性声明...........................................................i摘要...........................

2、.......................................iiAbstract..............................................................iii符号说明.............................................................iv前言.................................................................1第一章预备知识.......................

3、..............................3第二章图的邻点可区别无圈边染色...................................62.1一些联图的邻点可区别无圈边染色.......................................72.2一些幂图的邻点可区别无圈边染色.......................................12第三章图的邻点可区别E-全染色.....................................15第四章图的邻点可区别VE-全染色..........

4、.........................19第五章图的邻点可区别VI-全染色....................................235.1路、圈、完全图、轮和扇的邻点可区别VI-全染色........................235.2图的邻点可区别VI-全色数的一个上界....................................26参考文献.............................................................30攻读硕士学位期间完成的工作.......

5、..................................33致谢..................................................................341摘　要本文引入了图的邻点可区别无圈边染色、图的邻点可区别E-全染色、图的邻点可区别VE-全染色和图的邻点可区别VI-全染色的概念,并通过Lov´asz一般局部引理分别给出了它们色数的上界.第一部分给出了一些与概率方法相关的基本概念、定理和引理等预备知识;第二部分引入了图的邻点可区别无圈边染色的概念,用构造具体染色的方法给出了一些幂图Pnk、C

6、5kn、Wnk、Fnk和联图Pm∨Wn、Pm∨Fn、Pm∨Pn、Pm∨Sn、Cm;n的邻点可区别无圈边色数,且其均满足图的邻点可区别无圈边染色猜想;第三部分讨论了图的邻点可区别E-全染色,并用概率方法给出了图的邻点可区别E-全色数的一个上界;第四部分研究了图的邻点可区别VE-全染色,并用概率方法给出了图的邻点可区别VE-全色数的一个上界;第五部分给出了图的邻点可区别VI-全染色的概念,用构造具体染色的方法给出了一些简单图―路Pn,圈Cn,完全图Kn,轮Wn和扇Fn的邻点可区别VI-全色数,并用概率方法得到了一般图的邻点可区别的VI-全色数的一个上界.关

7、关关键键键词词词:Lov´asz一般局部引理;联图;幂图;邻点可区别无圈边染色;邻点可区别E-全染色;邻点可区别VE-全染色;邻点可区别VI-全染色iiAbstractIntroducetotheconceptsofadjacentvertex-distinguishingacyclicedgecoloring,ad-jacentvertex-distinguishingE-totalcoloring,adjacentvertex-distinguishingVE-totalcol-oringandadjacentvertex-distinguishi

8、ngVI-totalcoloringandobtainsomeupperboundsofthe