论文部分内容阅读
众所周知,四色定理是图论中的经典定理之一,这个定理可以解释为:每幅地图都可以用四种颜色着色,并且相邻的国家所着的颜色不同。因此,图的着色问题是图论中很重要的一个研究方向,人们对此进行了大量研究。目前,一些经典的着色问题仍在不断得到研究,而各种各样新的着色也层出不穷。 本文首先研究了20世纪80年代提出的强边着色问题.一个正常的边着色是指一个对边的着色满足任意两条相邻的边所着的颜色不同。一个图的强边着色指的是它的一个正常边着色满足任意两条与同一条边想邻时所着的颜色不同.也就是说,每个颜色类是一个导出的匹配.图 G的所有强边染色中所用颜色数的最小值k称作强边染色指数,用X1S(G)来表示.我们研究在最大平均度意义下的稀疏图的强边色数的上界.图 G的最大平均度mad(G)指它的所有子图的平均度的最大值,即此处为公式等证明了若图G的最大度△≥9且 mad(G)<8/3,则xS(G)≤3△-3;(2)若图 G的最大度△≥7, mad(G)≤3且没有3-正则子图,则 xSi(G)<3△。主要结果是:若图G的最大度△>7且 mad(G)<26/9,则 x1S(G)≤3△-1。对于研究各种染色来说,图的局部结构至关重要。如果我们对一个图的局部结构了解的越多越清楚,则可以让我们对染色问题的研究变得简单,得到更好的结果.而平面图是各种染色问题中常考虑的一个图类,因此人们对平面图的结构非常关注。局部结构是轻子图,即一个图包含特定的子图且子图的顶点的度数受到一定的限制.这里考虑的图类是最小度为5的平面图P5.图 H在图 G中的权(weight)是指图H的所有顶点在G中的度数之和.一个极小星指一个中心点的度数至多为5的星.设Ω△是最小的正整数k满足任意一个P5中的图均有一个极小星且它的权至多为k. Lebesgue在1940年给出了 P5包含的极小星的描述,由此可以得出Ω△≤△+31.最近,Borodin和Ivanova证明了当△≥13时,Ω△≤△+29.本文中,我们给出了两个有关P5的极小星的描述,第一个描述可以直接得出Borodin和 Ivanova的结果及之前已经证明的其他一些结果,第二个描述可以得出当△≥17时,Ω△≤△+28。