Bounds for the number of meeting edges in graph partitioning

Qinghou Zeng; Jianfeng Hou

Czechoslovak Mathematical Journal (2017)

  • Volume: 67, Issue: 3, page 741-752
  • ISSN: 0011-4642

Abstract

top
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 - Δ 1 ) / 2 + 2 w 2 / 3 , where w i is the total weight of edges of size i and Δ 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 - Δ 1 ) / 3 + 2 w 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 ⌈ 2 m / 5 ⌉ edges, which establishes a special case of a more general conjecture of Bollobás and Scott.

How to cite

top

Zeng, Qinghou, and Hou, Jianfeng. "Bounds for the number of meeting edges in graph partitioning." Czechoslovak Mathematical Journal 67.3 (2017): 741-752. <http://eudml.org/doc/294095>.

@article{Zeng2017,
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.},
author = {Zeng, Qinghou, Hou, Jianfeng},
journal = {Czechoslovak Mathematical Journal},
keywords = {graph; weighted hypergraph; partition; judicious partition},
language = {eng},
number = {3},
pages = {741-752},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Bounds for the number of meeting edges in graph partitioning},
url = {http://eudml.org/doc/294095},
volume = {67},
year = {2017},
}

TY - JOUR
AU - Zeng, Qinghou
AU - Hou, Jianfeng
TI - Bounds for the number of meeting edges in graph partitioning
JO - Czechoslovak Mathematical Journal
PY - 2017
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 67
IS - 3
SP - 741
EP - 752
AB - 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.
LA - eng
KW - graph; weighted hypergraph; partition; judicious partition
UR - http://eudml.org/doc/294095
ER -

References

top
  1. Alon, N., Bollobás, B., Krivelevich, M., Sudakov, B., 10.1016/S0095-8956(03)00036-4, J. Comb. Theory, Ser. B 88 (2003), 329-346. (2003) Zbl1030.05060MR1983363DOI10.1016/S0095-8956(03)00036-4
  2. Bollobás, B., Scott, A. D., 10.1007/s004939970002, Combinatorica 19 (1999), 473-486. (1999) Zbl0985.05028MR1773653DOI10.1007/s004939970002
  3. Bollobás, B., Scott, A. D., 10.1006/eujc.1998.0266, Eur. J. Comb. 21 (2000), 289-300. (2000) Zbl0943.05058MR1750165DOI10.1006/eujc.1998.0266
  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. (2002) Zbl1014.90082MR1919571
  5. Bollobás, B., Scott, A. D., 10.1002/rsa.10062, Random Struct. Algorithms 21 (2002), 414-430. (2002) Zbl1013.05059MR1945378DOI10.1002/rsa.10062
  6. Edwards, C. S., 10.4153/CJM-1973-048-x, Can. J. Math. 25 (1973), 475-485. (1973) Zbl0254.05116MR0337686DOI10.4153/CJM-1973-048-x
  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. Zbl0326.05115MR0398888
  8. Fan, G., Hou, J., 10.1002/rsa.20642, Random Struct. Algorithms 50 (2017), 59-70. (2017) Zbl1352.05150MR3583026DOI10.1002/rsa.20642
  9. Fan, G., Hou, J., Zeng, Q., 10.1016/j.dam.2014.07.002, Discrete Appl. Math. 179 (2014), 86-99. (2014) Zbl1303.05152MR3281184DOI10.1016/j.dam.2014.07.002
  10. Haslegrave, J., 10.1007/s00493-012-2696-x, Combinatorica 32 (2012), 451-471. (2012) Zbl1299.05184MR2965286DOI10.1007/s00493-012-2696-x
  11. Hou, J., Wu, S., Yan, G., 10.1016/j.jcta.2016.02.004, J. Comb. Theory Ser. A 141 (2016), 16-32. (2016) Zbl1334.05118MR3479236DOI10.1016/j.jcta.2016.02.004
  12. Hou, J., Zeng, Q., 10.1017/S0963548316000274, Comb. Probab. Comput. 26 (2017), 267-284. (2017) MR3603968DOI10.1017/S0963548316000274
  13. Liu, M., Xu, B., 10.1007/s10878-015-9828-3, J. Comb. Optim. 31 (2016), 1383-1398. (2016) Zbl1335.05095MR3480573DOI10.1007/s10878-015-9828-3
  14. Ma, J., Yen, P.-L., Yu, X., 10.1016/j.jctb.2010.06.002, J. Comb. Theory, Ser. B 100 (2010), 631-649. (2010) Zbl1208.05115MR2718683DOI10.1016/j.jctb.2010.06.002
  15. Ma, J., Yu, X., 10.1007/s00493-015-2944-y, Combinatorica 36 (2016), 537-556. (2016) MR3572424DOI10.1007/s00493-015-2944-y
  16. Scott, A., 10.1017/CBO9780511734885, Surveys in Combinatorics B. Webb Conf. Proc., Durham, 2005, London Mathematical Society Lecture Note Series 327, Cambridge University Press, Cambridge (2005), 95-117. (2005) Zbl1110.05084MR2187736DOI10.1017/CBO9780511734885
  17. Xu, X., Yan, G., Zhang, Y., 10.1007/s11425-015-5039-8, Sci. China, Math. 59 (2016), 609-616. (2016) Zbl1338.05219MR3457058DOI10.1007/s11425-015-5039-8
  18. Xu, B., Yu, X., 10.1016/j.jctb.2008.08.007, J. Comb. Theory, Ser. B 99 (2009), 324-337. (2009) Zbl1184.05099MR2482952DOI10.1016/j.jctb.2008.08.007
  19. Xu, B., Yu, X., 10.1017/S0963548311000204, Comb. Probab. Comput. 20 (2011), 631-640. (2011) Zbl1223.05245MR2805402DOI10.1017/S0963548311000204

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.