Geodesic
Bounds for the number of meeting edges in graph partitioning
Czechoslovak Mathematical Journal, Tome 67 (2017) no. 3, pp. 741-752
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/CMJ.2017.0147-16
Classification : 05C35, 05C75
Keywords: graph; weighted hypergraph; partition; judicious partition 
@article{10_21136_CMJ_2017_0147_16,
     author = {Zeng, Qinghou and Hou, Jianfeng},
     title = {Bounds for the number of meeting edges in graph partitioning},
     journal = {Czechoslovak Mathematical Journal},
     pages = {741--752},
     year = {2017},
     volume = {67},
     number = {3},
     doi = {10.21136/CMJ.2017.0147-16},
     mrnumber = {3697913},
     zbl = {06770127},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2017.0147-16/}
}
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
SP  - 741
EP  - 752
VL  - 67
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2017.0147-16/
DO  - 10.21136/CMJ.2017.0147-16
LA  - en
ID  - 10_21136_CMJ_2017_0147_16
ER  - 
%0 Journal Article
%A Zeng, Qinghou
%A Hou, Jianfeng
%T Bounds for the number of meeting edges in graph partitioning
%J Czechoslovak Mathematical Journal
%D 2017
%P 741-752
%V 67
%N 3
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2017.0147-16/
%R 10.21136/CMJ.2017.0147-16
%G en
%F 10_21136_CMJ_2017_0147_16
Zeng, Qinghou; Hou, Jianfeng. Bounds for the number of meeting edges in graph partitioning. Czechoslovak Mathematical Journal, Tome 67 (2017) no. 3, pp. 741-752. doi: 10.21136/CMJ.2017.0147-16

[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. | DOI | MR | JFM

[2] Bollobás, B., Scott, A. D.: Exact bounds for judicious partitions of graphs. Combinatorica 19 (1999), 473-486. | DOI | MR | JFM

[3] Bollobás, B., Scott, A. D.: Judicious partitions of 3-uniform hypergraphs. Eur. J. Comb. 21 (2000), 289-300. | DOI | MR | JFM

[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. | MR | JFM

[5] Bollobás, B., Scott, A. D.: Problems and results on judicious partitions. Random Struct. Algorithms 21 (2002), 414-430. | DOI | MR | JFM

[6] Edwards, C. S.: Some extremal properties of bipartite subgraphs. Can. J. Math. 25 (1973), 475-485. | DOI | MR | JFM

[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. | MR | JFM

[8] Fan, G., Hou, J.: Bounds for pairs in judicious partitions of graphs. Random Struct. Algorithms 50 (2017), 59-70. | DOI | MR | JFM

[9] Fan, G., Hou, J., Zeng, Q.: A bound for judicious $k$-partitions of graphs. Discrete Appl. Math. 179 (2014), 86-99. | DOI | MR | JFM

[10] Haslegrave, J.: The Bollobás-Thomason conjecture for 3-uniform hypergraphs. Combinatorica 32 (2012), 451-471. | DOI | MR | JFM

[11] Hou, J., Wu, S., Yan, G.: On judicious partitions of uniform hypergraphs. J. Comb. Theory Ser. A 141 (2016), 16-32. | DOI | MR | JFM

[12] Hou, J., Zeng, Q.: Judicious partitioning of hypergraphs with edges of size at most 2. Comb. Probab. Comput. 26 (2017), 267-284. | DOI | MR

[13] Liu, M., Xu, B.: On judicious partitions of graphs. J. Comb. Optim. 31 (2016), 1383-1398. | DOI | MR | JFM

[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. | DOI | MR | JFM

[15] Ma, J., Yu, X.: On judicious bipartitions of graphs. Combinatorica 36 (2016), 537-556. | DOI | MR

[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. | DOI | MR | JFM

[17] Xu, X., Yan, G., Zhang, Y.: Judicious partitions of weighted hypergraphs. Sci. China, Math. 59 (2016), 609-616. | DOI | MR | JFM

[18] Xu, B., Yu, X.: Judicious $k$-partitions of graphs. J. Comb. Theory, Ser. B 99 (2009), 324-337. | DOI | MR | JFM

[19] Xu, B., Yu, X.: Better bounds for $k$-partitions of graphs. Comb. Probab. Comput. 20 (2011), 631-640. | DOI | MR | JFM

Cité par Sources :