The Balanced Decomposition Number of TK4 and Series-Parallel Graphs

Shinya Fujita; Henry Liu

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 2, page 347-359
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Shinya Fujita, and Henry Liu. "The Balanced Decomposition Number of TK4 and Series-Parallel Graphs." Discussiones Mathematicae Graph Theory 33.2 (2013): 347-359. <http://eudml.org/doc/268334>.

@article{ShinyaFujita2013,
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.},
author = {Shinya Fujita, Henry Liu},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph decomposition; vertex colouring; k-connected; vertex coloring; -connected},
language = {eng},
number = {2},
pages = {347-359},
title = {The Balanced Decomposition Number of TK4 and Series-Parallel Graphs},
url = {http://eudml.org/doc/268334},
volume = {33},
year = {2013},
}

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
VL - 33
IS - 2
SP - 347
EP - 359
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) = 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.
LA - eng
KW - graph decomposition; vertex colouring; k-connected; vertex coloring; -connected
UR - http://eudml.org/doc/268334
ER -

References

top
  1. [1] B. Bollobás, Modern Graph Theory (Springer-Verlag, New York, 1998). 
  2. [2] R.J. Duffin, Topology of series-parallel networks, J. Math. Anal. Appl. 10 (1965) 303-318. Zbl0128.37002
  3. [3] E.S. Elmallah and C.J. Colbourn, Series-parallel subgraphs of planar graphs, Networks 22 (1992) 607-614. doi:10.1002/net.3230220608[Crossref] 
  4. [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[WoS][Crossref] Zbl1222.05210
  5. [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. Zbl1229.05229
  6. [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[Crossref] Zbl1178.05075

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.