In　2002,　Bollobás　and　Scott　posed　the　following　problem:　for　an　integer　(Formula　presented.)　and　a　graph　G　of　m　edges,　what　is　the　smallest　f(k,　m)　such　that　V(G)　can　be　partitioned　into　V　1,…,Vk　in　which　(Formula　presented.)　for　all　(Formula　presented.),　where　(Formula　presented.)　denotes　the　number　of　edges　with　both　ends　in　(Formula　presented.)　?　In　this　paper,　we　solve　this　problem　asymptotically　by　showing　that　(Formula　presented.).　We　also　show　that　V(G)　can　be　partitioned　into　(Formula　presented.)　such　that　(Formula　presented.)　for　(Formula　presented.),　where　Δ　denotes　the　maximum　degree　of　G.　This　confirms　a　conjecture　of　Bollobás　and　Scott.　©　2016　Wiley　Periodicals,　Inc.　Random　Struct.　Alg.,　50,　59–70,　2017.　©　2016　Wiley　Periodicals,　Inc.