On judicious bipartitions of graphs |
| |
Authors: | Jie Ma Xingxing Yu |
| |
Affiliation: | 1.School of Mathematical Sciences,University of Science and Technology of China,Hefei, Anhui,China;2.School of Mathematics,Georgia Institute of Technology Atlanta,Georgia,USA |
| |
Abstract: | For a positive integer m, let f(m) be the maximum value t such that any graph with m edges has a bipartite subgraph of size at least t, and let g(m) be the minimum value s such that for any graph G with m edges there exists a bipartition V (G)=V 1?V 2 such that G has at most s edges with both incident vertices in V i . Alon proved that the limsup of (fleft( m right) - left( {m/2 + sqrt {m/8} } right)) tends to infinity as m tends to infinity, establishing a conjecture of Erd?s. Bollobás and Scott proposed the following judicious version of Erd?s' conjecture: the limsup of (m/4 + left( {sqrt {m/32} - g(m)} right)) tends to infinity as m tends to infinity. In this paper, we confirm this conjecture. Moreover, we extend this conjecture to k-partitions for all even integers k. On the other hand, we generalize Alon's result to multi-partitions, which should be useful for generalizing the above Bollobás-Scott conjecture to k-partitions for odd integers k. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|