论文部分内容阅读
由于图论理论在现代应用数学中的重要作用以及计算机科学和组合优化的发展,图论作为数学科学中一门独立的学科飞速发展起来.图的染色问题是图论研究中一个非常活跃的领域,有着很好的理论探讨价值和实际意义.基于此,数学家们在传统的点染色,边染色的基础上添加各种限制,拓展出了许多新的染色分支. 赖宏建等人于2006年在《离散数学》上提出了条件染色的概念并得到了一些结论,在《图的条件染色》一文中,他们提出并讨论了一些特殊图类的条件色数,一般图的条件色数上界以及正常图的几个充分条件等.2002年,G.Hahn,J.Kratochvil,J.Siran,D.Sottean等人在《离散数学》上发表文章《图的单射色数》,在文中他们首次提出了单射染色.自此,在这个问题,特别是满足一定条件的平面图的单射色数方面,涌现出很多好的结果.2008年,孙磊,刘晓晓提出了邻域限制标号的概念,在刘晓晓的硕士毕业论文中,她研究了满足一定条件的图的邻域限制标号数下界,圈和树的邻域限制标号数以及邻域限制标号的几个性质等.这三类染色问题都是带有邻域限制的染色问题. 在本文第一章里,主要介绍了文章中涉及的一此基本概念与符号,描述了图的染色问题的发展及现状. 在第二章中,主要研究了图的条件染色问题,给出了正常图及r-正常图的几个充分条件并改讲了图的条件色数的上界. 在第三章中,主要研究了图的单射染色问题,介绍了在研究平面图中用到的一此特殊的概念,符号以及部分已有的研究成果.同时,给出了围长不小于6时图的单射色数的上界以及△=8和△=9时图的单射色数的特殊性质. 在第四章中,主要研究了图的邻域限制标号问题.对于图的邻域限制标号数,易见其有平凡的上下界2(△-1)≤ L1,2(G)≤ 2(n-1).在本章中我们给出了图的邻域限制标号数达到其平凡上下界的充要或充分条件,改进了非K2图的邻域限制标号数的上界并讨论了几个特殊图举的邻域限制标号数.