图的划分问题是指将图的顶点集按特定要求划分成点子集.经典的图染色问题是将图的顶点集划分成独立点集,而最大割问题则是寻求不同集合之间的边数达到最大的划分.我们主要研究的是两类划分问题,一类是图的染色问题,另一类则是公平划分问题.近年来,图染色问题被广泛研究.第二章主要研究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▽>4,或者不含4到6-圈且d≥ 3,则可平面图是3-可选的,其中d▽表示不同三角形之间的最短距离.我们降低了对d▽的限制,证明了:(1)当d≥ 2时,若不含4到6-圈和特殊的7-圈,或者(2)当d≥ 3时,若不含4-圈,5-圈和相邻的6-圈,则可平面图是3-可选的.在第四章,我们研究可平面的3-正则图的投影染色问题.图的投影染色与图的平方图的正常染色紧密相关.关于可平面图的平方图正常染色问题有著名的Wegner猜想.Thomassen[58]证明该猜想在可平面的3-正则图上是正确的.相比之下,关于可平面图投影染色的猜想在3-正则图上仍然无进展.我们证明了最小非5-投影可染的可平面3-正则图除一些特殊构形外都是3-连通的.论文的后半部分讨论了一些划分方面的问题.图的公平划分问题指的是寻找同时优化多个量的划分.近年来,这类问题被广泛地研究.Bollobas和Scott[8]提出问题:对于任一整数k ≥ 2和任一具有m条边的图,寻找最小的整数f(k,m)满足该图存在某一 kk划分(V1,V2,…,Vk),对于所有1≤i<j≤k都有e(Vi ∪ Vj)<f(k,m).马杰和郁星星[47]证明了 f(k,m)≤hkm+O(m4/5),其中hk<1.6/k,或者当k ≥ 23时,hk<1.5/k.最近,范更华和侯建锋[29]证明了 f(k,m)≤min{4/k2m+4△/k,m/k-1}+ o(m7/8).在第五章中,我们将误差项的指数7/8降低至5/6.超图的公平划分问题更加复杂.Bollobas和Scott[4]提出猜想:给定整数r ≥ 3和k≥ 2,任一具有m条边的r-一致超图H都存在某个fk-划分(V1,V2,…,Vk)使得每个e(Vi)≤mkr+ o(m).他们肯定了该猜想在r= 3时的正确性.最近侯建锋等人[36,70]证明了当△ = o(m)或者m=Ω(nr-3+∈)时,猜想也正确,其中∈为任意大于0的数.基于以上结论,我们自然地提出以下问题:对于任一整数k ≥ 3和1 ≤ l≤k-1,任一具有m条边的r-一致超图是否存在某个k-划分(V1,V2,...,Vk)使得对于它的任一 l元组(Vj,...,Vjl)都有e(Vj∪...∪Vjl)≤lr/krm+ o(m).注意到当l = k-1时,该问题对应到Bollobas和Scott的另一个关于相交问题的猜想.在第五章中,我们证明了若H为具有m条边的r-一致超图且△(H)=o(m),则H存在一个k-划分(V1,…,Vk)使得对于它的任一 l元组(Vj1,...,Vjl)都有e(Vj1 ∪…∪ Vjl)≤lr/krm + o(m).由此推出,H存在k-划分(V1,…,Vk)使得每个d(Vi)≥(1 + o(1))(1-(1-1/k)r)m.范更华和侯建锋[29]还证明了对于任一整数k≥2,任一具有m条边的图都存在一个k划分(V1,...,Vk)使得e(Vi∪Vj)≤m/k-1+o(m7/8),对于1≤i<j≤k.在第五章中,我们将此结果推广到r-一致超图:对于任一整数k ≥ 4和r ≥ 2,任一具有m条边的r-一致超图都存在一个k划分(V1,…,Vk)使得 e(Vi∪Vj)≤r-1/k-1m+ o(m),对于 1 ≤ i<j≤ k.范更华、侯建锋和郁星星[30]证明了不含4-圈的图G存在一个大小至少为m/2+n-1/4-|M|/2δ的二部平衡划分(其中M为图G的最大匹配),而围长至少为5的图存在一个大小至少为m/2 + n-1/4的二部平衡划分.第六章,我们得到了任意不含K2,i(i≥2为整数)的连通图G,若G是欧拉图,或者δ ≥ 2且不含距离为2三角形,则G存在一个大小至少为m/2+n-i+1/4二部平衡划分.并且设计了寻找不含4-圈的图具有最多自由顶点的最大匹配的算法.当考虑k-部平衡划分中最小化每部分内部边数的问题时,我们证明了当约束到n = o(m)或者△ = o(n)时,若n充分大,则G存在k-部平衡划分,使得每部分内部边数少于m/k2+ o(m).