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.

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

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 2010): 05C35, 05C75

DOI: 10.21136/CMJ.2017.0147-16

Full text available as PDF.


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


Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade. To activate your access, please contact Myris Trade at myris@myris.cz.
Subscribers of Springer need to access the articles on their site, which is https://link.springer.com/journal/10587.

[Previous Article] [Next Article] [Contents of This Number] [Contents of Czechoslovak Mathematical Journal]