Balanced decomposition of a vertex-colored graph

A balanced vertex-coloring of a graph GG is a function cc from V(G)V(G) to {−1,0,1}{−1,0,1} such that ∑{c(v):v∈V(G)}=0∑{c(v):v∈V(G)}=0. A subset UU of V(G)V(G) is called a balanced set if UU induces a connected subgraph and ∑{c(v):v∈U}=0∑{c(v):v∈U}=0. A decomposition V(G)=V1∪⋯∪VrV(G)=V1∪⋯∪Vr is called a balanced decomposition if ViVi is a balanced set for 1≤i≤r1≤i≤r.In this paper, the balanced decomposition number f(G)f(G) of GG is introduced; f(G)f(G) is the smallest integer ss such that for any balanced vertex-coloring cc of GG, there exists a balanced decomposition V(G)=V1∪⋯∪VrV(G)=V1∪⋯∪Vr with |Vi|≤s|Vi|≤s for 1≤i≤r1≤i≤r. Balanced decomposition numbers of some basic families of graphs such as complete graphs, trees, complete bipartite graphs, cycles, 2-connected graphs are studied.