Biased Partitions and Judicious k-Partitions of Graphs

发布时间：2019-04-01 10:03

【摘要】：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.
[Abstract]:Let G = (V, E) be a graph with m edges. For reals p 鈭，

本文编号：2451469