Further results on the balanced decomposition number

Research output: Contribution to journalArticle


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.
Original languageUnknown
Pages (from-to)119-128
JournalCongressus Numerantium
Issue numberNA
Publication statusPublished - 1 Jan 2010

Cite this