论文部分内容阅读
染色问题具有重要的实用价值和理论意义,一直是图论中的主要研究课题之一.本文主要研究图的染色问题,具体地说,本文主要讨论以下几个问题:(1)近几年高考的一个热点问题一关于3×n方格的染色问题;(2)图的邻点可区别全染色,邻强边染色,均匀邻强边染色,点边邻点可区别全染色,关联邻点可区别全染色,邻点强可区别全染色的问题,计算出相应的色数,并给出具体的染色方案.本文分三章进行讨论:
在第一章中,我们简述图论相关领域的研究现状,介绍本文研究的主要目的并给出主要结论.
在第二章中,我们介绍相关概念,猜想,引理,常用术语及符号.
在第三章中,第一节,用图论的最新理念,利用树形结构分层分类分析,得到了用m种不同的颜色染3×n个方格,使每个格子染一种颜色且相邻的格子染不同的颜色的方法数的两个新结论,第二节,研究路和圈的倍图的邻强边染色,路的倍图的均匀邻强边染色,得到相应的色数,并给出具体的染色方案,第三节,研究项链的邻点可区别全染色,点边邻点可区别全染色,关联邻点可区别全染色,得到它们的色数分别是5,3,4,并给出具体的染色方案,第四节,研究路和圈的中间图的邻点强可区别全染色并得到它们的邻点强可区别全染色数.第五节,讨论幂图pkn(k=2,3)的点可区别全染色和C3n的邻点可区别全染色.