Czechoslovak Mathematical Journal, Vol. 67, No. 3, pp. 741-752, 2017


Bounds for the number of meeting edges in graph partitioning

Qinghou Zeng, Jianfeng Hou

Received March 25, 2016.   First published July 14, 2017.

Abstract:  Let $G$ be a weighted hypergraph with edges of size at most 2. Bollobás and Scott conjectured that $G$ admits a bipartition such that each vertex class meets edges of total weight at least $(w_1-\Delta_1)/2+2w_2/3$, where $w_i$ is the total weight of edges of size $i$ and $\Delta_1$ is the maximum weight of an edge of size 1. In this paper, for positive integer weighted hypergraph $G$ (i.e., multi-hypergraph), we show that there exists a bipartition of $G$ such that each vertex class meets edges of total weight at least $(w_0-1)/6+(w_1-\Delta_1)/3+2w_2/3$, where $w_0$ is the number of edges of size 1. This generalizes a result of Haslegrave. Based on this result, we show that every graph with $m$ edges, except for $K_2$ and $K_{1,3}$, admits a tripartition such that each vertex class meets at least $\lceil{2m}/5\rceil$ edges, which establishes a special case of a more general conjecture of Bollobás and Scott.
Keywords:  graph; weighted hypergraph; partition; judicious partition
Classification MSC:  05C35, 05C75


References:
[1] N. Alon, B. Bollobás, M. Krivelevich, B. Sudakov: Maximum cuts and judicious partitions in graphs without short cycles. J. Comb. Theory, Ser. B 88 (2003), 329-346. DOI 10.1016/S0095-8956(03)00036-4 | MR 1983363 | Zbl 1030.05060
[2] B. Bollobás, A. D. Scott: Exact bounds for judicious partitions of graphs. Combinatorica 19 (1999), 473-486. DOI 10.1007/s004939970002 | MR 1773653 | Zbl 0985.05028
[3] B. Bollobás, A. D. Scott: Judicious partitions of 3-uniform hypergraphs. Eur. J. Comb. 21 (2000), 289-300. DOI 10.1006/eujc.1998.0266 | MR 1750165 | Zbl 0943.05058
[4] B. Bollobás, A. D. Scott: Better bounds for Max Cut. Contemporary Combinatorics B. Bollobás Bolyai Soc. Math. Stud. 10, János Bolyai Math. Soc., Budapest (2002), 185-246. MR 1919571 | Zbl 1014.90082
[5] B. Bollobás, A. D. Scott: Problems and results on judicious partitions. Random Struct. Algorithms 21 (2002), 414-430. DOI 10.1002/rsa.10062 | MR 1945378 | Zbl 1013.05059
[6] C. S. Edwards: Some extremal properties of bipartite subgraphs. Can. J. Math. 25 (1973), 475-485. DOI 10.4153/CJM-1973-048-x | MR 0337686 | Zbl 0254.05116
[7] C. S. Edwards: An improved lower bound for the number of edges in a largest bipartite subgraph. Recent Advances in Graph Theory Proc. Symp., Praha 1974, Academia, Praha (1975), 167-181. MR 0398888 | Zbl 0326.05115
[8] G. Fan, J. Hou: Bounds for pairs in judicious partitions of graphs. Random Struct. Algorithms 50 (2017), 59-70. DOI 10.1002/rsa.20642 | MR 3583026 | Zbl 1352.05150
[9] G. Fan, J. Hou, Q. Zeng: A bound for judicious $k$-partitions of graphs. Discrete Appl. Math. 179 (2014), 86-99. DOI 10.1016/j.dam.2014.07.002 | MR 3281184 | Zbl 1303.05152
[10] J. Haslegrave: The Bollobás-Thomason conjecture for 3-uniform hypergraphs. Combinatorica 32 (2012), 451-471. DOI 10.1007/s00493-012-2696-x | MR 2965286 | Zbl 1299.05184
[11] J. Hou, S. Wu, G. Yan: On judicious partitions of uniform hypergraphs. J. Comb. Theory Ser. A 141 (2016), 16-32. DOI 10.1016/j.jcta.2016.02.004 | MR 3479236 | Zbl 1334.05118
[12] J. Hou, Q. Zeng: Judicious partitioning of hypergraphs with edges of size at most 2. Comb. Probab. Comput. 26 (2017), 267-284. DOI 10.1017/S0963548316000274 | MR 3603968
[13] M. Liu, B. Xu: On judicious partitions of graphs. J. Comb. Optim. 31 (2016), 1383-1398. DOI 10.1007/s10878-015-9828-3 | MR 3480573 | Zbl 1335.05095
[14] J. Ma, P.-L. Yen, X. Yu: On several partitioning problems of Bollobás and Scott. J. Comb. Theory, Ser. B 100 (2010), 631-649. DOI 10.1016/j.jctb.2010.06.002 | MR 2718683 | Zbl 1208.05115
[15] J. Ma, X. Yu: On judicious bipartitions of graphs. Combinatorica 36 (2016), 537-556. DOI 10.1007/s00493-015-2944-y | MR 3572424
[16] A. Scott: Judicious partitions and related problems. Surveys in Combinatorics B. Webb Conf. Proc., Durham, 2005, London Mathematical Society Lecture Note Series 327, Cambridge University Press, Cambridge (2005), 95-117. DOI 10.1017/CBO9780511734885 | MR 2187736 | Zbl 1110.05084
[17] X. Xu, G. Yan, Y. Zhang: Judicious partitions of weighted hypergraphs. Sci. China, Math. 59 (2016), 609-616. DOI 10.1007/s11425-015-5039-8 | MR 3457058 | Zbl 1338.05219
[18] B. Xu, X. Yu: Judicious $k$-partitions of graphs. J. Comb. Theory, Ser. B 99 (2009), 324-337. DOI 10.1016/j.jctb.2008.08.007 | MR 2482952 | Zbl 1184.05099
[19] B. Xu, X. Yu: Better bounds for $k$-partitions of graphs. Comb. Probab. Comput. 20 (2011), 631-640. DOI 10.1017/S0963548311000204 | MR 2805402 | Zbl 1223.05245

Affiliations:   Qinghou Zeng, Jianfeng Hou, Center for Discrete Mathematics, Fuzhou University, Tongpan, Software Road 89-1, Fuzhou 350003, Fujian, P. R. China, e-mail: qinghouzeng@hotmail.com, jfhou@fzu.edu.cn


 
PDF available at: