Geodesic
The Balanced Decomposition Number of $ TK_4 $ and Series-Parallel Graphs
Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 2, pp. 347-359.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: graph decomposition, vertex colouring, k-connected 
@article{DMGT_2013_33_2_a8,
     author = {Fujita, Shinya and Liu, Henry},
     title = {The {Balanced} {Decomposition} {Number} of $ TK_4 $ and {Series-Parallel} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {347--359},
     publisher = {mathdoc},
     volume = {33},
     number = {2},
     year = {2013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2013_33_2_a8/}
}
TY  - JOUR
AU  - Fujita, Shinya
AU  - Liu, Henry
TI  - The Balanced Decomposition Number of $ TK_4 $ and Series-Parallel Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2013
SP  - 347
EP  - 359
VL  - 33
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2013_33_2_a8/
LA  - en
ID  - DMGT_2013_33_2_a8
ER  - 
%0 Journal Article
%A Fujita, Shinya
%A Liu, Henry
%T The Balanced Decomposition Number of $ TK_4 $ and Series-Parallel Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2013
%P 347-359
%V 33
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2013_33_2_a8/
%G en
%F DMGT_2013_33_2_a8
Fujita, Shinya; Liu, Henry. The Balanced Decomposition Number of $ TK_4 $ and Series-Parallel Graphs. Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 2, pp. 347-359. http://geodesic.mathdoc.fr/item/DMGT_2013_33_2_a8/

[1] B. Bollobás, Modern Graph Theory (Springer-Verlag, New York, 1998).

[2] R.J. Duffin, Topology of series-parallel networks, J. Math. Anal. Appl. 10 (1965) 303-318.

[3] E.S. Elmallah and C.J. Colbourn, Series-parallel subgraphs of planar graphs, Networks 22 (1992) 607-614. doi:10.1002/net.3230220608

[4] S. Fujita and H. Liu, The balanced decomposition number and vertex connectivity, SIAM. J. Discrete Math. 24 (2010) 1597-1616. doi:10.1137/090780894

[5] S. Fujita and H. Liu, Further results on the balanced decomposition number, in: Proceedings of the Forty-First Southeastern International Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. 202 (2010) 119-128.

[6] S. Fujita and T. Nakamigawa, Balanced decomposition of a vertex-coloured graph, Discrete Appl. Math. 156 (2008) 3339-3344. doi:10.1016/j.dam.2008.01.006