On a conjecture on the balanced decomposition number

The concept of balanced decomposition number was introduced by Fujita and Nakamigawa in connection with a simultaneous transfer problem. A balanced colouring of a graph G is a pair (R,B) of disjoint subsets R,B⊆V(G) with |R|=|B|. A balanced decomposition D of a balanced colouring C=(R,B) of G is a partition of vertices V(G)=V1∪V2∪⋯∪Vr such that G[Vi] is connected and |Vi∩R|=|Vi∩B| for 1≤i≤r. Let C be the set of all balanced colourings of G and D(C) be the set of all balanced decompositions of G for C∈C. Then the balanced decomposition number f(G) of G is f(G)=maxC∈CminD∈D(C)max1≤i≤r|Vi|. Fujita and Nakamigawa conjectured that if G is a 2-vertex connected graph of n vertices, then f(G)≤⌊n2⌋+1. In this paper, we confirm this conjecture in the affirmative.