On Colorings And Partitions Of Graphs

The classical coloring of graphs asks for a partition of vertices into stable sets and the Max Cut problem asks for a partition with maximum number of edges between different sets.In this thesis,we are concerning with two kinds of partition problems.One is the graph coloring problem,the other is the judicious partition problem.In chapter 2,we investigate the edge coloring of 1-planar graphs.A graph is 1-planar if it can be drawn on the plane such that each edge is crossed by at most one other edge.Zhang and Wu[79]studied the edge coloring of 1-planar graphs and proved that every 1-planar graph with ?(G)? 10 is of class one.There are also some partial results while the maximum degree is at most 9:a 1-planar graph of maximum degree ? is of class one if(1)it has no chordal 5-cycles and ?? 9[81],or(2)it has no adjacent triangles and ?? 8[82],or(3)it has no triangle and ?? 7[78].Recently,Zhang[80]constructed 1-planar graphs of class two which have maximum degree 6 or 7 and contain adjacent triangles.We prove that every 1-planar graph G of maximum degree 7 with neither inter-secting triangles nor chordal 5-cycles is of class one.In Chapter 3,we consider the list coloring of planar graphs.Thomassen showed that every planar graph is 5-choosable[56]and every planar graph without 3-and 4-cycles is 3-choosable[57].Voigt presented a non-4-choosable planar graph[63]and a triangle-free planar graph with list chromatic number 4[64].Voigt[65]also constructed a non-3-choosable planar graph without cycles of length 4 and 5.So,Steinberg's Conjecture does not extend to 3-choosability.Montassier et al.[49]showed that every planar graph in which the 5--cycles are at distance at least 4 from each other is 3-choosable.They[48]also showed that a planar graph is 3-choosable if it has neither 4-nor 5-cycles and d?? 4,or it has no 4-to 6-cycles and d?? 3,where d? denotes the minimum distance between different triangles.We reduce the restrictions on dv and prove that every planar graph with d??2,without cycles of length from 4 to 6,and without some special 7-cycles,is 3-choosable.We also show that every planar graph with dv>3,without cycles of length from 4 to 5,and without adjacent 6-cycles,is 3-choosable.In chapter 4,we investigate the injective vertex coloring of planar cubic graphs.Injective coloring of graphs is closely related with proper vertex coloring of the square of graphs.Thomassen[58]confirmed the well-known Wegner's conjecture on planar cubic graphs.By contrast,the similar conjecture about injective coloring is still open even on planar cubic graphs.We show that every minimum non-5-injective colorable planar cubic graph is 3-connected except some special configurations.The judicious partition problem is to find a partition optimizing several quantities simultaneously.This kind of problems were investigated extensively in the recent years.Bollobas and Scott[8]asked a question:for every integer k ? 2,what is the smallest integer f(k,m)such that every graph of m edges admits a k-partition(V1 V2,...,Vk)in which e(V1 ? Vj)? f(k,m)for all 1 ? i<j ?k?Ma and Yu[47]proved that f(k,m)? hkm+ O(m4/5),where hk<1.6/k,and hk<1.5/k if k?23.Recently,Fan and Hou[29]proved that each graph G with m edges and maximum degree ? admits a k-partition(V1,V2,...,Vk)with e(Vi ? Vj)?min{4/k2m+4?/k,m/k-1} + o(m7/8)for all 1 ?i?j?k.In chapter 5,we improve the parameter 7/8 to 5/6.Bollobas and Scott[4]conjectured that every r-uniform hypergraph H of m edges has a partition(V1,V2,...,Vk)such that e(Vi)?m/k? +o(m),for each i?[k],where r ? 3 and k ? 2 are fixed integers,and they confirmed the case that r = 3.Recently,Hou,Wu and Yan[36,70]confirmed this conjecture when ? = o(m),or m =?(nr-3+?)for any given ?>0.Based on these conclusions,it is natural to ask that for every pair of integers k? 3 and 1 ?l?k-1,whether every r-uniform hypergraph H of m edges has a partition(V1,V2,...,Vk)such that e(Vjk ?...? Vji)?l?/krm+ o(m)for each l-tuple(Vj1,...,Vjl),In the case that l ?k-1,its truthness implies the validity of another conjecture of Bollobas and Scott.In chapter 5,we prove that if H is an r-uniform hypergraph of m edges with?(H)= o(m),then H admits a k-partition(V1,...,Vk)such thate(Vj1 U...U Vji)?l?/k?m+ o(m)for each l-tuple(Vj1,...,Vjl)with 1 ?l?k-1.Meanwhile,H admits a k-partition(V1,...,Vk)such that d(Vi)?(1+o(1))(1-(1-1/k)r)m for each i?[k].Fan and Hou[29]proved that each graph of m edges admits a k-partition(V1,...,Vk)such that e(Vi U Vj)?m/k-1+ o(m7/8)for all 1 ? i<j ? k.In chapter 5,we extend this result to r-uniform hypergraphs:each r-uniform hypergraph with m edges admits a k-partition(V1,...,Vk).such that e(Vi ? Vj)?r-1/k-1m+ o(m)for all 1?i<j ?k,where k? 4 and r ? 2 are integers.Fan,Hou and Yu[30]showed that every graph G without 4-cycles admits a bisection of size at least m/2+n-1/4-|M|/2?(where M is a maximum matching in G),and every graph G with girth at least 5 admits a bisection of size at least m/2+n-1/4.In Chapter 6,we get that each connected graph G with ??2 and without K2,i(i>2 being an integer)admits a bisection(V1,V2)with e(V1,V2)?m/2+n-i+1/4,if either G has no triangles at distance 2,or G is Eulerian.Then we present an algorithm finding the maximum matching with the largest number of free vertices of graphs without 4-cycles.When considering the problem of finding a balanced k-partition(V1,...,Vk)minimizing maxi?[k]{e(Vi)},we get that,restricting to n = o(m)or ? = o(n),G admits a balanced k-partition such that the number of edges in each part is less than m/k2?o(m),if n is sufficient large.