Graph partitions. II (Q2744384)

[For Part I see \textit{T. D. Porter}, J. Comb. Math. Comb. Comput. 15, 111-118 (1994; Zbl 0806.05032).]NEWLINENEWLINENEWLINEFor a graph \(G\), let \(e(U_i)\) denote the number of edges of the induced subgraph \(G[U_i]\). Let \(\gamma_k(G)\) denote the minimum of \(\max^k_{i=1}e (U_i)\), where \(U_1,U_2, \dots,U_k\) is a \(k\)-partition of the vertex set of \(G\), and the minimum is taken for all \(k\)-partitions of the vertex set. It is shown that for graphs with \(m\) edges \(\gamma_2 (G)\leq {m\over 4}+\sqrt{{m\over 18}}\); and if \(k\) is a power of 2, then \(\gamma_k (G)\leq {m\over k^2}+ 1.3081{\sqrt m\over k}\). See \textit{B. Bollobás} and \textit{A. D. Scott} [Combinatorica 19, No. 4, 473-486 (1999; Zbl 0985.05028)] for a better (in a sense, optimal) bound on \(\gamma_2(G)\) and related results.