Bounds for the number of meeting edges in graph partitioning

Title:

Bounds for the number of meeting edges in graph partitioning

Creator:

Zeng, Qinghou and Hou, Jianfeng

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:c007c075-e67e-47ec-963f-4d8bf9da26eb
uuid:c007c075-e67e-47ec-963f-4d8bf9da26eb
issn:0011-4642

Subject:

matematika, mathematics, graph, weighted hypergraph, partition, judicious partition, 13, and 51

Type:

model:article and TEXT

Format:

print, bez média, and svazek

Description:

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., Qinghou Zeng, Jianfeng Hou., and Obsahuje bibliografické odkazy

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

741-752

Source:

Czechoslovak Mathematical Journal | 2017 Volume:67 | Number:3

Harvested from:

CDK

Metadata only:

false