图的染色与划分问题研究

发布时间：2020-04-11 22:41

【摘要】：图的划分问题是指将图的顶点集按特定要求划分成点子集.经典的图染色问题是将图的顶点集划分成独立点集,而最大割问题则是寻求不同集合之间的边数达到最大的划分.我们主要研究的是两类划分问题,一类是图的染色问题,另一类则是公平划分问题.近年来,图染色问题被广泛研究.第二章主要研究1-可平面图的边染色问题.1-可平面图是指可被嵌入到平面中使得每条边被其余至多一条边穿过的图.该图类是由Ringle首次引入.著名的Vizing边染色定理表明每个图都满足边色数等于△或者△ +1,分别对应第一类图和第二类图.张欣和吴建良[79]证明了当△(G)≥ 10时,任何1-可平面图都满足边色数等于△(G).当最大度至多为9时,已得到在一些限制条件下的1-可平面图是第一类的:(1)[81]不含弦5-圈且△ ≥ 9,或者(2)[82]不含相邻三角形且△ ≥ 8,或者(3)[78]不含三角形且△ ≥ 7.最近,张欣[80]构造了包含相邻三角形且最大度为6或7的第二类1-可平面图.在第二章,我们证明了不含相交三角形和弦5-圈且最大度为7的1-可平面图是第一类的.在第三章,我们考虑了可平面图的列表染色问题.给图G的每个顶点v一个颜色集合L(v),形成图G的一个列表分派L.给定图G 一个列表分派L,每个元素u ∈ V从其所分派颜色集合L(v)中选取颜色的正常染色,就是图G的一个L-染色.若任意给定的列表分派L且每个u ∈ V的颜色集合都有|L(v)|≥ k,图G都有一个L-染色,则称图G是k-可选色的.满足图G是k-可选色的最小k值,是图G的列表染色数或选色数,记作χlist(G).Thomassen[56]证明了所有可平面图都是5-可选的,[57]还证明了所有不含3-圈和4-圈的可平面图是3-可选的.Voigt[63]找出一个非4-可选的可平面图,和一个列表色数为4的不含三角形的可平面图[64].她[65]还构造了一个不含4圈和5圈的非3-可选的可平面图,所以著名的Steinberg猜想不能推广至3-可选的情形.Montassier等人[49]证明了任一5--圈的距离至少为4的可平面图是3-可选的.他们[48]也证明了若不含4-圈和5-圈且d%，

本文编号：2623929