将图的顶点集或边集按特定要求划分成点子集或边子集的问题称为图的划分问题。图的划分问题首先关注的是满足条件的划分的存在性.如果这些划分存在，进一步的工作就是在这些划分上优化某些成本函数。图的划分问题已在算法和结构方面得到很广泛的研究。　　图的划分问题有很多，其中就包括比较关注的图的染色问题。例如，经典的顶点染色问题就是将图的顶点划分成独立点集的图的划分问题。　　图G的一个k-染色是顶点V(G)到S的一个映射，其中S={f1，2，…，k}是颜色集合。图G的一个k-染色被称为正常染色当且仅当G中任意相邻顶点染不同的颜色。类似地，可以定义边染色和全染色。　　图的列表染色或者图选色是图染色的一个自然推广。本文中，研究了曲面嵌入图的边选色，全选色和其他一些染色问题。　　二部子图问题是所关注的另一类图的划分问题。设S，T是图G的一个划分。用记号(S，T)G表示由图G中S，T之间的边构成的二部子图。众所周知，(S，T)G的最小度能超过图G最小度的一半。于是一个有趣的问题是图G[S]，G[T]和(S，T)G的最小度或连通度能否同时达到一个比较大的值。最近，Kiihn和Osthus给出了一个否定的结论。那么，如果在上述问题中只要求(S，T)G的一部的最小度或连通度达到一个比较大的值会怎么样呢?Kiihn和Osthus的回答是肯定的。　　对任意正整数l，他们证明了存在整数k1(l)≤211·3l2和k2(l)≤216l2，当δ(G)≥k1(l)时，存在划分将V(G)分成S和T使得δ(G[S])≥l≤δ(G[T])且S中的每个点在T都至少有l个邻点；当图的连通度大于k2(l)时，V(G)可以划分成S和T，使得G[S]和G[T]都是l-连通的且S中每个点在T中都至少有l个邻点。　　在第二章中，首先在一般图上改进了Ktihn和Osthus的结果，将k1(l)的上界改进到24·17l2。接着考虑了无三圈图。通过证明平均度至少是8/3l的无三圈图有l-连通的子图，在无三圈图中将k2(l)的上界改进到216·3-3·l2。　　设G是有m条边的图，P∈[0，1]，q=1-p。有偏的二部划分问题要求将图的顶点集V(G)划分成V1，V2两部分，同时最小化qe(V1)+pe(V2)的值。设mp(G)=minV(G)=V1∪V2qe(V2)。以概率p随机地在V(G)中选择顶点，可以很容易得到一个划分V1，V2，使得qe(V1)+pe(V2)≤pqm对α>0，Bollobás和Scott证明了若mp(G)=pqm-α则G存在一个好的公平划分V1，V2使得e(V2)≤p2m-α+√32mp2+16α2/q3m，且e(V2)≤q2m-α+√32mq2+16α2/q3m。　　受Bolloás和Scott的启发，考虑最大化qe(V1)+pe(V2)的有偏划分问题。类似地，设mp(G)=maxV(G)=V1∪V2pe(V1)+(V2)。通过类似于mp(G)的讨论，易证m(G)≥pqm。　　在第三章中，证明了如果mp(G)≥pqm+α，那么G存在使得e(V1)，e(V2)都不太小的二部划分V1，V2。也部分改进了Balloás和Scott的结果。　　在第四章中，主要讨论了可嵌入曲面图的列表全染色和列表边染色。　　图G=(V，E)的一个к-全染色指的是最多用к种颜色对图G的顶点和边染色，使得相邻的和相关联的元素都染不同色。图G的全色数指的是使得图G有后一全染色的最小忌值，记作x(G)。图G的一个全列表分派L是指给图G的每个属于于V∪E中的元素x一个颜色集合L(x)。给图G一个全列表分派L，图G的一个L-全染色是指每个元素z∈V∪E从其所分派颜色集合L(x)中选取颜色的正常全染色。如果对于任意给定的全列表分派L且每个X∈V∪E的颜色集合都有|L(x)|≥к，图G都有一个L-全染色，则称图G是к-全可选色的。图G的列表全染色数或全选色数指的是使得图G是к-全可选色的最小к值，记作xl(G)。类似地，可以定义列表边染色。通常用xl(G)表示图G的列表边染色数或边选色数，用x(G)表示图G的边色数。显然，xl(G)≥x(G)≥△+1，xl(G)≥x(G)≥△。　　如果两圈有公共顶点，则称两圈相交。首先证明了对任意没有相交三角形的轮胎图G，若△(G)≥6，则x1(G)≤△(G)+1，Xl"(G)≤△(G)+2；若△(G)≥8，则xl(G)=△(G)。　　如果图中两圈有一条公共边，则称该两圈相邻接。设图是没有3-圈邻接4-圈的平面图。证明了当△(G)≥6时，xl(G)≤△(G)+2；当△(G)≥8时，xl(G)=△(G)且xl(G)=△(G)+1。　　在第五章中讨论了平面图的列表投影染色。若图G的一个点染色使得有公共邻点的点染不同颜色，则称该染色为投影染色。图G可投影染色所需的最小颜色数称为投影染色数，记作xi(G)。给图G一个列表分派L，图G的一个L-投影染色是指每个点都从其所分派颜色集合中选取颜色的投影染色。如果对于任意给定的全列表分派L且每个u∈V的颜色集合都有|L(u)|≥к，图G都有一个L-投影染色，则称图G是к-投影可选色的。图G的列表投影染色数或投影选色数指的是使得图G是к-投影可选色的最小к值，记作xli(G)。　　设G是最大度为△(G)围长为g的平面图。定义mad(G)=max{2|E(H)/|V(H)|：H是G的子图}。本章中，证明了(1)对任何mad(G)<10/3的图G，当△(G)≥30时，)(xli(G)≤△(G)+4；当△(G)≥18时，xli(G)≤△A(G)+5；当△(G)≥14时，xli(G)≤△(G)+6；(2)如果mad(G)<3且A(G)≥12，则xli(G)≤A(G)+2。文章的最后，给出一些可进一步研究的问题。