摘要
本文考虑的都是无向的、有限的简单图.给定图G=（V，E）,用|G|,△（G）分别表示G的顶点数和最大度.如果阶为n+1（n≥3）的3-连通图G中有一个顶点v∈V（G）使得G-v是一个长度为n的圈Cn,且点v的度为n,则称G是一个n-轮图，并记为Wn.如果图G可以经过删除点、边和收缩边得到图H，则称H是G的一个子式.本文主要研究无W5或W4子式图的边染色和全染色问题. 图G的k-边染色是指用k种颜色对E（G）中的所有边染色，使得任意相邻边都不同色，这个最小整数k称为G的边色数，并记作x''（G）.关于求解图的边色数问题，Vizing和Gupta分别独立证明了:对任何简单图G,都有x''（G）∈{△（G）,△（G）+1}.这样所有图就可以分为两类:满足x''（G）=△（G）的图称作是第1类的;否则是第2类的.已经证明图的分类问题本身是一个NP-完全问题，因此判断图属于哪一类的结果几乎都是一些充分条件，所得的研究也较为广泛且成果颇丰.1965年，Vizing在证明了最大度至少为8的平面图是第1类的这一结果之时，一并提出了著名的平面图边染色猜想:每个满足△（G）≥6的平面图都是第1类的.2001年，Sanders和Zhao证明了所有△（G）=7的平面图都是第1类的.目前该猜想只剩下△（G）=6的情况未被解决.2021年，Feng,Gao和Wu将上述两个结果成功扩展到了无K5子式图，并得到了:任意△（G）≥7的无K5子式图也是第1类的.除此之外，对于无W3子式图，即系列平行图，它的分类问题已经得到了完全刻画，其结果就是:除奇圈外的所有连通的系列平行图都是第1类的. 基于以上结果，本文考虑无W5子式图和无W4子式图的边染色，获得的结果如下: （1）对于任意满足△（G）≥5的无W5子式的图G,有x''（G）=△（G）; （2）对于任意满足△（G）≥4的无W4子式的图G,有x''（G）=△（G）. 同时很容易验证:完全图K5是第2类的，K4和八面体（即正文的图1-2里的图G10）剖分任何一条边后得到的图都是第2类的.所以上面的结论（1）和（2）相对最大度来说都是最好的. 图G的k-全染色是指用k种颜色对V（G）UE（G）中的所有元素染色，使得任意两个相邻或关联元素都不同色.保证G有一个k-全染色的最小整数k称为其全色数，并用x"（G）表示.参考图的边染色的结果，Vizing和Behzad分别独立提出了图的全染色猜想:对于任意图G，△（G）+1≤x"（G）≤△（G）+2.下界显然是成立的，但上界目前只被证明对△（G）≤5的图是成立的.如果仅限制在平面图上，那么图的全染色有一系列的结果.2022年，Yang和Wu得到了:对于无K5子式图G,x"（G）≤max{9,△（G）+2}和x"（G）≤max{11,△（G）+1}.2004年，Wu证明了:对所有最大度至少为3的系列平行图G，有x"（G）=△（G）+1. 本文同样考虑无W5子式图和无W4子式图的全染色，获得的结果如下: （3）对于任意满足△（G）≥6的无W5子式的图G,有x"（G）=△（G）+1; （4）对于任意满足△（G）≥5的无W4子式的图G,有x"（G）=△（G）+1. 同时，结合全染色猜想对于最大度至多为5的图是成立的，结论（3）也说明无W5子式图确实满足全染色猜想.
NETL