### Abstract

Original language | Unknown |
---|---|

Pages (from-to) | 347-359 |

Journal | Discussiones Mathematicae Graph Theory |

Volume | 33 |

Issue number | 2 |

DOIs | |

Publication status | Published - 1 Jan 2013 |

### Keywords

### Cite this

}

*Discussiones Mathematicae Graph Theory*, vol. 33, no. 2, pp. 347-359. https://doi.org/10.7151/dmgt.1666

**The balanced decomposition number of TK_4 and series-parallel graphs.** / Liu, Henry Chung Hang.

Research output: Contribution to journal › Article

TY - JOUR

T1 - The balanced decomposition number of TK_4 and series-parallel graphs

AU - Liu, Henry Chung Hang

PY - 2013/1/1

Y1 - 2013/1/1

N2 - 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) = {V_1,...,V_r} such that, for every i, 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 in 2008. They conjectured that f(G) ≤ ⌊n/2⌋ + 1 if G is a 2-connected graph on n vertices. In this paper, we shall prove two partial results, in the cases when G is a subdivided K_4, and a 2-connected series-parallel graph.

AB - 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) = {V_1,...,V_r} such that, for every i, 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 in 2008. They conjectured that f(G) ≤ ⌊n/2⌋ + 1 if G is a 2-connected graph on n vertices. In this paper, we shall prove two partial results, in the cases when G is a subdivided K_4, and a 2-connected series-parallel graph.

KW - Graph decomposition

KW - vertex colouring

KW - k-connected.

U2 - 10.7151/dmgt.1666

DO - 10.7151/dmgt.1666

M3 - Article

VL - 33

SP - 347

EP - 359

JO - Discussiones Mathematicae Graph Theory

JF - Discussiones Mathematicae Graph Theory

SN - 1234-3099

IS - 2

ER -