论文部分内容阅读
本文研究嵌入图以及平面图的子图结构以及在着色上的应用一些问题．在文章[88]中，Zhao考虑了一类可嵌入在可定向曲面(欧拉特征值σ≤0)并且不包含短圈的图。Zhao证明了任意的可嵌人在可定向曲面(欧拉特征值σ≤0)并且不包含从4到11-12σ圈的图是可3-着色的并且提出一个问题能够保证不包含从4到k(∑)-圈的图是可3-着色的最小的整数k(∑)是多少?受到这个问题的启发，考虑K(∑)=11-3σ并且得到一个Lebesgue形式的定理．g<,σ>表示可嵌入在可定向曲面(欧拉特征值σ≤0)并且不包含从4到11-3σ圈的图。得到的以下主要结果：
定理2.1 G是一个嵌入在可定向曲面(欧拉特征值σ≤0)并且没有相邻的三面．如果G不包含从4到11-3σ的面，要么G包含一个2<->-度点或者包含一个light(12-3σ)<+>-面。
作为子图light(12-3<,Xσ>)<+>-面的应用，证明定理2.2如果G∈g<,σ>，那么G is 3-可着色的．
考虑了平面图的3-可着色。在1976，Steinberg给出一个猜想任意不包含4-圈和5-圈的平面图是3-可着色的。而这个条件就必要的，因为已经找到不可3-着色的平面图要么包含4-圈或者包含5-圈(见K<,4>和[34]中的例子[Fig.2])。由于直接证明的困难性，许多人考虑了一些特殊的平面图。在这里，考虑一类平面图不包含相邻三面并且不包含{5，6，9}-圈。得到一个Lebcsgue形式的定理并验证这类平面图是可3-着色的。
定理3.1 G是一个2-连通的平面图不包含相邻三面并且不包含{5，6，9}-圈那么必有以下结论成立：
(1)δ(G)<3；
(2)G包含一个4一面；
(3)G包含一个special 10-面关联于十个3-度点并且与五个3-面相邻。作为定理3.1的应用，得到下面的结论定理3.2任何平面图不包含相邻三面并且不包含{5，6，9}-圈是可3-着色的。
关于平面图，有一个猜想：是否任意的3-可着色的平面图的点荫度不超过2。受到这个猜想和Steinberg猜想的启发，考虑了不包含短圈的平面图的点荫度问题。证明了一个Lebcsgue形式的结构定理并把这个结论应用在不包含4-圈的平面图上。定理4.1 G是一个不包含4-面并且不包含相邻三面的平面图．如果δ(G)=4，那么G包含一个F<3><,5>导出子图。
应用定理4.1结果，给出了文章[46]的简短证明作为引理4．2并且得到不包含4-圈的平面图的点荫度不超过2作为定理4．3。
引理4.2如果G是一个不包含4-圈的平面图，那么G是4-可选色性的。
定理4.3如果G是一个不包含4-圈的平面图，那么a(G)≤2．接着我们使用移权法和反证法完成了以下结论的证明：
定理4.4如果G是一个不包含3-圈的平面图，那么a(G)≤2．
定理4.5如果G是一个不包含5-圈的平面图，那么a(G)≤2．
定理4.3，4.4和4.5可视为对上面猜想的是否正确的一个正面支持．
关于平面图的平方图，在[76]，Wegner提出了以下猜想：
猜想5.1[76]对于一个平面图G，受到Wegner猜想的启发，考虑了不包含3-圈的平面图的着色性．下面是已知的关于平面图的平方图的着色性：
采用g表示不包含三角形的平面图的集合。证明了一个Lebesgue形式的定理从而得到g的一个固定结构并且利用这个性质我们找到了这类平面图的平方图的可选色性的一个上界。称一个4-面f是特殊的如果f关联于两个2-度点并且称一个点v是大点如果v是一个15<+>-度点。称一个大点v是轻的如果d<,G<2>＞(u)≤△(G)+13．记τ<,2>(v)和τ<,3>(v)分别为与v相邻的2-度点和3-度点的个数。
定理5.1如果G∈g并且δ(G)≥2，那么必有以下结论成立：
(a)一个14<->-度点与一个2-度点相邻.
(b)如果v是一个大点并且v至少关联于d(v)-7特殊的4-面，那么τ<,2>(v)=d(v)或有0<τ<,3>(v)=d(v)-τ<,2>(v)≤7并有一个3-度点属于N(v)并且这个3-度点关联于两个4-面，这两个4-面均关联于2-度点．
(c)有一个路P<,3>=xyz其中d(y)=3并且d(x)+d(z)≤15．
作为定理5.1的应用，得到下面的定理；
定理5.2对于G∈g要么G包含一个轻的大点要么x(G<2>)≤△(G)+16.
最后，着重进一步考虑了以下内容： (i)平面图的非正则着色；(ii)平面图和嵌入图的平方图的着色问题； (iii)L(p，q)-着色问题．