A balanced colouring of a graph G is a colouring of some of the vertices of G with two colours, say red and blue, such that there is the same number of vertices in each colour. The balanced decomposition number f(G) of G is the minimum integer s with the following property: For any balanced colouring of G, there is a partition V(G) = V1 \cup ... \cup Vr such that, for every 1 ≤ i ≤ r, V i induces a connected subgraph of order at most s, and contains the same number of red and blue vertices. The function f(G) was introduced by Fujita and Nakamigawa, and was further studied by Fujita and Liu. Fujita and Nakamigawa conjectured that f(G) ≤ [n/2] + 1 if G is a 2-connected graph on n vertices. Partial results of this conjecture have been proved. In this paper, we shall prove another partial result, in the case when the number of coloured vertices is six. We shall also derive some consequences from known results about the balanced decomposition number and other results.
|Publication status||Published - 1 Jan 2010|