IC-平面图的可区别染色

来源 :河北工业大学 | 被引量 : 0次 | 上传用户:xqjulia
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的染色理论起源于1852年Frederick Guthrie提出的四色问题.图的染色理论是图论中非常重要的一个分支,并且应用十分广泛.近些年来,学者们对图染色的研究不仅限于图的点染色、边染色和全染色,也在此基础上提出了一些新的染色.图的邻点可区别边染色是在图的正常边染色上添加限制条件的一种染色,它要求正常边染色满足对图中任意一对相邻的顶点u和v,与u关联的所有边所染颜色构成的集合不同于与v关联的所有边所染颜色构成的集合.2002年张忠辅等人最先研究了这一染色并提出了关于图的邻点可区别边染色的猜想,即对于阶至少是6的连通图G,Δ(G)+2种颜色可以保证G具有一个邻点可区别边染色,其中Δ(G)表示图G的最大度.并且他们证明了这一猜想对某些特殊图是成立的.图的邻和可区别全染色是在图的正常全染色上添加限制条件的一种染色,它要求正常全染色满足对图中任意一对相邻的顶点u和v,点u以及与点u关联的所有边所染颜色的和不同于点v以及与点v关联的所有边所染颜色的和.2015年Pilsniak和Wozniak研究了这一染色并提出了关于图的邻和可区别全染色的猜想,即对任意的图G,Δ(G)+3种颜色可以保证G具有一个邻和可区别全染色,其中Δ(G)表示图G的最大度.并且他们也证明了这一猜想对某些特殊图是成立的.在这两个猜想提出后,一些学者致力于研究对于其他图这些猜想是否成立.本文研究了 IC-平面图的上述两种染色.IC-平面图是平面图的推广,是1-平面图的子类.对IC-平面图的研究具有较强的实际意义,它与电路布局问题和防火问题等密切相关.通过反证法、组合零点定理和权转移等方法,本文证明了上述两个猜想对于某些IC-平面图是成立的.主要研究内容及结果如下:1.利用反证等方法研究了最大度至少为13的IC-平面图的结构性质,用权转移的方法证明了该类图满足图的邻和可区别全染色猜想.2.利用组合零点定理等方法研究了最大度至少为10且不含相邻三角形的IC-平面图的结构性质,用权转移的方法证明了该类图满足图的邻和可区别全染色猜想.3.利用重染等方法研究了最大度至少为10且不含三角形的IC-平面图的的结构性质,用权转移的方法证明了该类图满足图的邻点可区别边染色猜想.
其他文献
学位
学位
学位
学位
学位
学位
学位
学位
学位
学位