Maximum balanced 3-partitions of graphs (Q2875685)

A \(k\)-partition of vertices of a graph is balanced if the number of vertices in two distinct terms of the \(k\)-partition differ in size at most 2. It is proved that if \(G\) is a graph with \(m\) edges and \(r\) is the maximum number of vertex disjoint paths of length 2, then \(G\) contains a balanced 3-partition \(V_1, V_2, V_3\) such that \(e(V_1, V_2, V_3) \geq (2m + 2r)/3\). Actually, a slightly stronger result can be proved using additional parameters such as the number of edges in a maximal disjoint matching from the vertex disjoint paths of length 2. Also it is proved for any \(3 \leq p < 6\) that there are sufficient conditions in terms of the minimum degree \(\delta(G)\) and maximum degree \(\Delta(G)\) such that there is a balanced 3-partition with \(\max \{e(V_1), e(V_2), e(V_3)\} \leq m/p\).