| Title:
|
Bounds for the number of meeting edges in graph partitioning (English) |
| Author:
|
Zeng, Qinghou |
| Author:
|
Hou, Jianfeng |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
67 |
| Issue:
|
3 |
| Year:
|
2017 |
| Pages:
|
741-752 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
graph |
| Keyword:
|
weighted hypergraph |
| Keyword:
|
partition |
| Keyword:
|
judicious partition |
| MSC:
|
05C35 |
| MSC:
|
05C75 |
| idZBL:
|
Zbl 06770127 |
| idMR:
|
MR3697913 |
| DOI:
|
10.21136/CMJ.2017.0147-16 |
| . |
| Date available:
|
2017-09-01T12:23:33Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/146856 |
| . |
| Reference:
|
[1] Alon, N., Bollobás, B., Krivelevich, M., Sudakov, B.: Maximum cuts and judicious partitions in graphs without short cycles.J. Comb. Theory, Ser. B 88 (2003), 329-346. Zbl 1030.05060, MR 1983363, 10.1016/S0095-8956(03)00036-4 |
| Reference:
|
[2] Bollobás, B., Scott, A. D.: Exact bounds for judicious partitions of graphs.Combinatorica 19 (1999), 473-486. Zbl 0985.05028, MR 1773653, 10.1007/s004939970002 |
| Reference:
|
[3] Bollobás, B., Scott, A. D.: Judicious partitions of 3-uniform hypergraphs.Eur. J. Comb. 21 (2000), 289-300. Zbl 0943.05058, MR 1750165, 10.1006/eujc.1998.0266 |
| Reference:
|
[4] Bollobás, B., Scott, A. D.: Better bounds for Max Cut.Contemporary Combinatorics B. Bollobás Bolyai Soc. Math. Stud. 10, János Bolyai Math. Soc., Budapest (2002), 185-246. Zbl 1014.90082, MR 1919571 |
| Reference:
|
[5] Bollobás, B., Scott, A. D.: Problems and results on judicious partitions.Random Struct. Algorithms 21 (2002), 414-430. Zbl 1013.05059, MR 1945378, 10.1002/rsa.10062 |
| Reference:
|
[6] Edwards, C. S.: Some extremal properties of bipartite subgraphs.Can. J. Math. 25 (1973), 475-485. Zbl 0254.05116, MR 0337686, 10.4153/CJM-1973-048-x |
| Reference:
|
[7] Edwards, C. S.: 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. Zbl 0326.05115, MR 0398888 |
| Reference:
|
[8] Fan, G., Hou, J.: Bounds for pairs in judicious partitions of graphs.Random Struct. Algorithms 50 (2017), 59-70. Zbl 1352.05150, MR 3583026, 10.1002/rsa.20642 |
| Reference:
|
[9] Fan, G., Hou, J., Zeng, Q.: A bound for judicious $k$-partitions of graphs.Discrete Appl. Math. 179 (2014), 86-99. Zbl 1303.05152, MR 3281184, 10.1016/j.dam.2014.07.002 |
| Reference:
|
[10] Haslegrave, J.: The Bollobás-Thomason conjecture for 3-uniform hypergraphs.Combinatorica 32 (2012), 451-471. Zbl 1299.05184, MR 2965286, 10.1007/s00493-012-2696-x |
| Reference:
|
[11] Hou, J., Wu, S., Yan, G.: On judicious partitions of uniform hypergraphs.J. Comb. Theory Ser. A 141 (2016), 16-32. Zbl 1334.05118, MR 3479236, 10.1016/j.jcta.2016.02.004 |
| Reference:
|
[12] Hou, J., Zeng, Q.: Judicious partitioning of hypergraphs with edges of size at most 2.Comb. Probab. Comput. 26 (2017), 267-284. MR 3603968, 10.1017/S0963548316000274 |
| Reference:
|
[13] Liu, M., Xu, B.: On judicious partitions of graphs.J. Comb. Optim. 31 (2016), 1383-1398. Zbl 1335.05095, MR 3480573, 10.1007/s10878-015-9828-3 |
| Reference:
|
[14] Ma, J., Yen, P.-L., Yu, X.: On several partitioning problems of Bollobás and Scott.J. Comb. Theory, Ser. B 100 (2010), 631-649. Zbl 1208.05115, MR 2718683, 10.1016/j.jctb.2010.06.002 |
| Reference:
|
[15] Ma, J., Yu, X.: On judicious bipartitions of graphs.Combinatorica 36 (2016), 537-556. MR 3572424, 10.1007/s00493-015-2944-y |
| Reference:
|
[16] Scott, A.: 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. Zbl 1110.05084, MR 2187736, 10.1017/CBO9780511734885 |
| Reference:
|
[17] Xu, X., Yan, G., Zhang, Y.: Judicious partitions of weighted hypergraphs.Sci. China, Math. 59 (2016), 609-616. Zbl 1338.05219, MR 3457058, 10.1007/s11425-015-5039-8 |
| Reference:
|
[18] Xu, B., Yu, X.: Judicious $k$-partitions of graphs.J. Comb. Theory, Ser. B 99 (2009), 324-337. Zbl 1184.05099, MR 2482952, 10.1016/j.jctb.2008.08.007 |
| Reference:
|
[19] Xu, B., Yu, X.: Better bounds for $k$-partitions of graphs.Comb. Probab. Comput. 20 (2011), 631-640. Zbl 1223.05245, MR 2805402, 10.1017/S0963548311000204 |
| . |
