论文部分内容阅读
图的着色问题一直是图论中的重要问题，并且在离散数学和组合分析中有着广泛的应用。很多领域所涉及的问题都与图的着色理论相关，例如：排序问题、排课表问题、存储问题等等，正是由于着色的理论意义和实用价值引起了世人的广泛的兴趣。本文主要研究一般图和Sierpi(n)ski图S(n，k)的{Pr}-自由着色并且研究了{P3}-自由着色在标号问题中的应用。具体研究内容如下：
首先，综述了一般图的着色的概念和研究现状，例如：顶点着色、无圈着色、2-距离着色、星着色以及L(2，1)-标号等，对于这些着色与标号的研究方法可直接应用于图的{Pr}-自由着色，从而为后文的研究做一些铺垫。
其次，根据2-距离着色和星着色的特点，文章引入了{Pr}-自由着色：一个图G的{Pr}-自由着色是正常的顶点着色并且使得长为r-1的路上不能着双色。首先通过运用线图构造了一类特殊图，证明了最大度为△的图G的{P3}-自由色数的下界，见定理3.5，然后通过运用概率的方法证明了最大度为△的图G的{P4}-自由色数，见定理3.13，从而推广了文献[1]中的最主要结果。
最后，首先证明了特殊图Sierpi(n)ski图S(n，k)的{Pr}-自由色数并且给出了精确值，然后给出了{P3}-自由着色的一个在标号问题上的应用。通过S(n，k)的{P3}-自由着色，给出了S(n，k)的L(2，1)-标号数并且证明了此标号是均匀的，从而引入了均匀L(2，1)-标号的概念(一个图G的均匀L(2，1)-标号是正常的L(2，1)-标号并且使得任意的两个不同标号的顶点数至多相差为1)，并且给出了S(n，k)的均匀L(2，1)-标号数的值。