×

A note on balanced bipartitions. (English) Zbl 1219.05147

Summary: A balanced bipartition of a graph \(G\) is a bipartition \(V_{1}\) and \(V_{2}\) of \(V(G)\) such that \(- 1\leq |V_{1}| - |V_{2}|\leq 1\). Bollobás and Scott conjectured that if \(G\) is a graph with \(m\) edges and minimum degree at least 2 then \(G\) admits a balanced bipartition \(V_{1},V_{2}\) such that \(\max \{ e(V_{1}),e(V_{2}) \} \leq m/3\), where \(e(V_i)\) denotes the number of edges of \(G\) with both ends in \(V_i\). In this note, we prove this conjecture for graphs with average degree at least 6 or with minimum degree at least 5. Moreover, we show that if \(G\) is a graph with \(m\) edges and \(n\) vertices, and if the maximum degree \(\Delta (G)=o(n)\) or the minimum degree \(\delta (G)\rightarrow \infty \), then \(G\) admits a balanced bipartition \(V_{1},V_{2}\) such that \(\max \{ e(V_{1}),e(V_{2}) \} \leq (1+o(1))m/4\), answering a question of Bollobás and Scott in the affirmative. We also provide a sharp lower bound on \(\max \{ e(V_{1},V_{2}):V_{1},V_{2}\) is a balanced bipartition of \(G \}\), in terms of size of a maximum matching, where \(e(V_{1},V_{2})\) denotes the number of edges between \(V_{1}\) and \(V_{2}\).

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bollobás, B.; Scott, A. D., Judicious partitions of graph, Period. Math. Hungar., 26, 125-137 (1993) · Zbl 0796.05056
[2] Bollobás, B.; Scott, A. D., Exact bounds for judicious partitions of graphs, Combinatorica, 19, 473-486 (1999) · Zbl 0985.05028
[3] Bollobás, B.; Scott, A. D., Problems and results on judicious partitions, Random Structures Algorithms, 21, 414-430 (2002) · Zbl 1013.05059
[4] Bollobás, B.; Scott, A. D., (Better bounds for max cut, in Contemporary Comb. Better bounds for max cut, in Contemporary Comb, Bolyai Soc Math Stud, vol. 10 (2002), János Bolyai Math Soc.: János Bolyai Math Soc. Budapest), 185-246 · Zbl 1014.90082
[5] Bollobás, B.; Scott, A. D., Judicious partitions of bounded-degree graphs, J. Graph Theory, 46, 131-143 (2004) · Zbl 1048.05067
[6] Edmonds, J., Maximum matching and a polyhedron with \((0, 1)\) vertices, J. Res. Natl. Bur. Stand., 69, 125-130 (1965) · Zbl 0141.21802
[7] Edwards, C. S., Some extremal properties of bipartite graphs, Canad. J. Math., 25, 475-485 (1973) · Zbl 0254.05116
[8] C.S. Edwards, An improved lower bound for the number of edges in a largest bipartite subgraph, in: Proc. 2nd Czechoslovak Symposium on Graph Theory, Prague, 1975, pp. 167-181.; C.S. Edwards, An improved lower bound for the number of edges in a largest bipartite subgraph, in: Proc. 2nd Czechoslovak Symposium on Graph Theory, Prague, 1975, pp. 167-181. · Zbl 0326.05115
[9] Porter, T. D., On a bottleneck bipartition conjecture of Erdős, Combinatorica, 12, 317-321 (1992) · Zbl 0767.05059
[10] Porter, T. D.; Székely, L. A., On a matrix discrepancy problem, Congr. Numer., 73, 239-248 (1990) · Zbl 0695.05028
[11] Scott, A. D., Judicious partitions and related problems, (Surveys in Combinatorics. Surveys in Combinatorics, London Math. Soc. Lecture Notes Ser., vol. 327 (2005), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 95-117 · Zbl 1110.05084
[12] Shahrokhi, F.; Székely, L. A., The complexity of the bottleneck graph bipartition problem, J. Combin. Math. Combin. Comput., 15, 221-226 (1994) · Zbl 0942.68581
[13] Thomassen, C., On the max-cut problem for a planar, cubic, triangle-free graph, and the Chinese postman problem for a planar triangulation, J. Graph Theory, 53, 261-269 (2006) · Zbl 1109.05039
[14] Xu, B.; Yu, X., Judicious \(k\)-partitions of graphs, J. Combin. Theory Ser. B, 99, 324-337 (2009) · Zbl 1184.05099
[15] Xu, B.; Yan, J.; Yu, X., Balanced judicious partitions of graphs, J. Graph Theory, 63, 210-225 (2010) · Zbl 1215.05093
[16] Yan, J.; Xu, B., Balanced judicious partitions of \((k, k - 1)\)-biregular graphs, J. Nanjing Norm. Univ. Nat. Sci. Ed., 31, 24-28 (2008) · Zbl 1199.05296
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.