DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 33(2) (2013) 347-359
DOI: https://doi.org/10.7151/dmgt.1666

The Balanced Decomposition Number of TK4 and Series-parallel Graphs

Shinya Fujita

Department of Integrated Design Engineering
Maebashi Institute of Technology
460-1 Kamisadori, Maebashi, 371-0816, Japan

Henry Liu

Departamento de Matemática
Faculdade de Ciências e Tecnologia
Universidade Nova de Lisboa
Quinta da Torre, 2829-516 Caparica, Portugal

Abstract

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.

Keywords: graph decomposition, vertex colouring, k-connected

2010 Mathematics Subject Classification: 05C15, 05C40, 05C70.

References

[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.

Received 24 September 2011
Revised 13 April 2012
Accepted 16 April 2012

Close