The balanced decomposition number of TK_4 and series-parallel graphs

Research output: Contribution to journalArticle

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) = {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.
Original languageUnknown
Pages (from-to)347-359
JournalDiscussiones Mathematicae Graph Theory
Volume33
Issue number2
DOIs
Publication statusPublished - 1 Jan 2013

Keywords

    Cite this

    @article{a4ee2e820d184dfd85f666a7901bc3ee,
    title = "The balanced decomposition number of TK_4 and series-parallel graphs",
    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) = {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.",
    author = "Liu, {Henry Chung Hang}",
    year = "2013",
    month = "1",
    day = "1",
    doi = "10.7151/dmgt.1666",
    language = "Unknown",
    volume = "33",
    pages = "347--359",
    journal = "Discussiones Mathematicae Graph Theory",
    issn = "1234-3099",
    publisher = "University of Zielona Gora",
    number = "2",

    }

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

    In: Discussiones Mathematicae Graph Theory, Vol. 33, No. 2, 01.01.2013, p. 347-359.

    Research output: Contribution to journalArticle

    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 -