Bounds for the number of meeting edges in graph partitioning

Zeng, Qinghou ; Hou, Jianfeng

Czechoslovak Mathematical Journal, Tome 67 (2017) no. 3, pp. 741-752.

Résumé

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.

Détail

DOI : 10.21136/CMJ.2017.0147-16

Classification : 05C35, 05C75
Keywords: graph; weighted hypergraph; partition; judicious partition