Maximum balanced 3-partitions of graphs
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\).
- Perfectly balanced partitions of smoothed graphs
- Triangle-factors in a balanced blown-up triangle
- Balanced graph partitions
- Tripartite multidigraphs and imbalances
- Generating all patterns of graph partitions within a disparity bound
- Balanced partitions of 3-colored geometric sets in the plane
- On locally-balanced 2-partitions of some classes of graphs
This page was built for publication: Maximum balanced 3-partitions of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875685)
