A balanced coloring of a graph G is an ordered pair (R,B) of disjoint subsets R,B⊆V(G) with |R|=|B| . The balanced decomposition number f(G) of a connected graph G is the minimum integer f such that for any balanced coloring (R,B) of G there is a partition P of V(G) such that S induces a connected subgraph with |S|≤f and |S∩R|=|S∩B| for S∈P . This paper gives a short proof for the result by Fujita and Liu (2010) that a graph G of n vertices has f(G)=3 if and only if G is ⌊n2⌋ -connected but is not a complete graph.
關聯:
Journal of Combinatorial Optimization 28(2), p.505-510
