学位论文 > 优秀研究生学位论文题录展示

联图的全染色及邻点可区别全染色

作　者: 孟献青
导　师: 王世英
学　校: 山西大学
专　业: 应用数学
关键词: 联图 全染色 邻点可区别全染色 全色数 邻点可区别全色数
分类号: O157.5
类　型: 硕士论文
年　份: 2007年
下　载: 71次
引　用: 1次
阅　读: 论文下载
 

内容摘要


染色问题一直是图论中的热点话题之一，它在组合分析和实际中有着非常广泛的应用，比如时间表问题、贮藏问题及电网络问题等。本文分为四章，主要研究了图的全染色及邻点可区别全染色。第一章对本文所用的术语、记号和结论作了总结。第二章主要研究了一种特殊联图的全染色，全染色的概念是Behzad M．在1965年提出的，全染色是指对图G的顶点和边同时染色，使得任意相邻或相关联的元素（顶点和边）均染有不同的颜色；全染色所用颜色的最少数目称为图G的全色数，记为χT（G）．之后，Behzad又提出了全染色猜想：对于任意简单图G，有χT（G）≤△（G）+2．Sánchez-Arroyo[25]证明了判断χT（G）=△（G）+1是NP-完全的，目前已经证明了全染色猜想对于一些特殊的图族是成立的，包括完全γ—部图，最大度至少是8的平面图，本章根据联图的结构和全染色的定义，得到了联图Cn∨Kn的全色数，从而证明了全染色猜想在这种特殊联图中的正确性。第三章和第四章主要研究了两种联图的邻点可区别全染色，邻点可区别全染色的定义是张忠辅在2004年提出来的，其内容为：设G是阶至少为2的简单连通图，k是正整数，f是V（G）∪E（G）到{1，2，…，k}的映射，对任意u∈V（G），记C（u）={f（u）}∪{f（uv）|uv∈E（G），v∈V（G）}．如果（1）对任意uv，uw∈E（G），u≠w，有f（uv）≠f（vw）；（2）对任意uv∈E（G），有f（u）≠f（v），f（u）≠f（uv），f（v）≠f（uv），则称f为G的k-正常全染色，进一步，如果f还满足（3）对任意uv∈E（G），有C（u）≠C（v），则称f为G的k-邻点可区别全染色（简记为k-AVDTC），称min{k|G有k-邻点可区别全染色}为G的邻点可区别全色数，记为χat（G），其中C（u）称为点u在f下的色集合，在第三章中，我们运用归纳法思想，得出了Wm∨Pn的邻点可区别全色数，第四章我们在联图Wm∨Pn的基础上，仍然运用归纳法思想，得出了Wm∨Cn的邻点可区别全色数，主要结果如下：定理对联图Cn∨Kn（n≥5），有χT（Cn∨Kn）=△+1．定理对联图Wm∨Pn（m≥3），有定理对联图Wm∨Cn（m≥3，n≥3），有

全文目录


相似论文

  1. 若干图类的Smarandachely邻点全染色,O157.5
  2. 最大度为6的平面图的全染色,O157.5
  3. 关于几类图的分数色数与分数全色数的研究,O157.5
  4. 若干图类的均匀邻强边染色,O157.5
  5. 图的点可区别边染色的一些结果,O157.5
  6. 几类图的邻点可区别全染色,O157.5
  7. 若干图类的强边着色,O157.5
  8. 关于图的邻点可区别全染色的一些结果,O157.5
  9. 一些图的点邻点可区别全染色,O157.5
  10. 若干图类的新染色问题,O157.5
  11. 图的（p，1）-全标号及图的弱邻点可区分的染色问题,O157.5
  12. 联图与笛卡尔积图类的交叉数研究,O157.5
  13. 几类图的泛宽度染色和（p,1）—全标号,O157.5
  14. 关于图的交叉数研究,O157.5
  15. 图的边共染色的若干结果,O157.5
  16. 若干图类的星边染色,O157.5
  17. 一些图类的保Wiener指数的树,O157.5
  18. 几类联图的全着色研究,O157.5
  19. 图的模linkage研究,O157.5
  20. 四类图的邻点可区别全染色,O157.5
  21. 特殊平面图的全染色,O157.5

中图分类: > 数理科学和化学 > 数学 > 代数、数论、组合理论 > 组合数学（组合学） > 图论
© 2012 www.xueweilunwen.com