Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648992 | Discrete Mathematics | 2010 | 13 Pages |
Abstract
In this paper we study the following problem of Bollobás and Scott: What is the smallest f(k,m) such that for any integer kâ¥2 and any graph G with m edges, there is a partition V(G)=âi=1kVi such that for 1â¤iâ jâ¤k, e(ViâªVj)â¤f(k,m)? We show that f(k,m)<1.6m/k+o(m), and f(k,m)<1.5m/k+o(m) for kâ¥23. (While the graph K1,n shows that f(k,m)â¥m/(kâ1), which is 1.5m/k when k=3.) We also show that f(4,m)â¤m/3+o(m) and f(5,m)â¤4m/15+o(m), providing evidence to a conjecture of Bollobás and Scott. For dense graphs, we improve the bound to 4m/k2+o(m), which, for large graphs, answers in the affirmative a related question of Bollobás and Scott.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Jie Ma, Xingxing Yu,