The Balanced Decomposition Number of TK4 and Series-Parallel Graphs
Discussiones Mathematicae Graph Theory, Tome 33 (2013) no. 2, p. 347.

Voir la notice de l'article dans European Digital Mathematics Library

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 ∪˙ · · · ∪˙ Vr such that, for every i, Vi 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 K4, and a 2-connected series-parallel graph.
Classification : 05C15, 05C40, 05C70
Mots-clés : graph decomposition, vertex colouring, k-connected, vertex coloring, -connected 
@article{DMGT_2013__33_2_268334,
     author = {Shinya Fujita and Henry Liu},
     title = {The {Balanced} {Decomposition} {Number} of {TK4} and {Series-Parallel} {Graphs}},
     journal = {Discussiones Mathematicae Graph Theory},
     pages = {347},
     publisher = {mathdoc},
     volume = {33},
     number = {2},
     year = {2013},
     zbl = {1293.05105},
     language = {en},
     url = {https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_2_268334/}
}
TY  - JOUR
AU  - Shinya Fujita
AU  - Henry Liu
TI  - The Balanced Decomposition Number of TK4 and Series-Parallel Graphs
JO  - Discussiones Mathematicae Graph Theory
PY  - 2013
SP  - 347
VL  - 33
IS  - 2
PB  - mathdoc
UR  - https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_2_268334/
LA  - en
ID  - DMGT_2013__33_2_268334
ER  - 
%0 Journal Article
%A Shinya Fujita
%A Henry Liu
%T The Balanced Decomposition Number of TK4 and Series-Parallel Graphs
%J Discussiones Mathematicae Graph Theory
%D 2013
%P 347
%V 33
%N 2
%I mathdoc
%U https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_2_268334/
%G en
%F DMGT_2013__33_2_268334
Shinya Fujita; Henry Liu. The Balanced Decomposition Number of TK4 and Series-Parallel Graphs. Discussiones Mathematicae Graph Theory, Tome 33 (2013) no. 2, p. 347. https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_2_268334/