Biased Partitions and Judicious k-Partitions of Graphs  

作　　者：Qing Hou ZENG Jian Feng HOU Jin DENG Xia LEI 

机构地区：[1]Center for Discrete Mathematics, Fuzhou University, Fuzhou 350003, P. R. China [2]Hu'nan College of Information, Changsha 410200, P. R. China [3]School of Software Engineering, Xiamen University of Technology, Xiamen 361024, P. R. China

出　　处：《Acta Mathematica Sinica,English Series》2017年第5期668-680,共13页数学学报（英文版）

基　　金：Supported by NSFC(Grant No.11671087);New Century Programming of Fujian Province(Grant No.JA14028)

摘　　要：Let G =（V, E） be a graph with m edges. For reals p ∈ [0, 1] and q = 1-p, let m;（G） be the minimum of qe（V;） + pe（V;） over partitions V = V;∪ V;, where e（V;） denotes the number of edges spanned by V;. We show that if m;（G） = pqm-δ, then there exists a bipartition V;, V;of G such that e（V;） ≤ p;m-δ + p（m/2）;+ o（√m） and e（V;） ≤ q;m-δ + q（m/2）;+ o（√m） for δ = o(m;). This is sharp for com;lete graphs up to the error term o（√m）. For an integer k ≥ 2, let fk（G） denote the maximum number of edges in a k-partite subgraph of G. We prove that if fk（G） =（1-1/k）m + α,then G admits a k-partition such that each vertex class spans at most m/k;-Ω(m/k;) edges forα = Ω（m/k;）. Both of the above im;rove the results of Bollob′as and Scott.Let G =(V, E) be a graph with m edges. For reals p ∈ [0, 1] and q = 1-p, let m_p(G) be the minimum of qe(V_1) + pe(V_2) over partitions V = V_1 ∪ V_2, where e(V_i) denotes the number of edges spanned by V_i. We show that if m_p(G) = pqm-δ, then there exists a bipartition V_1, V_2 of G such that e(V_1) ≤ p^2m-δ + p(m/2)^(-1/2)+ o(√m) and e(V_2) ≤ q^2m-δ + q(m/2)^(-1/2) + o(√m) for δ = o(m^(2/3)). This is sharp for com_plete graphs up to the error term o(√m). For an integer k ≥ 2, let fk(G) denote the maximum number of edges in a k-partite subgraph of G. We prove that if fk(G) =(1-1/k)m + α,then G admits a k-partition such that each vertex class spans at most m/k^2-Ω(m/k^(7.5)) edges forα = Ω(m/k^6). Both of the above im_prove the results of Bollob′as and Scott.

关 键 词：GRAPH MAX-CUT biased partition judicious partition 

分 类 号：O157.5[理学—数学]