- Tytuł:
- The Balanced Decomposition Number of $ TK_4 $ and Series-Parallel Graphs
- Autorzy:
-
Fujita, Shinya
Liu, Henry - Powiązania:
- https://bibliotekanauki.pl/articles/30146584.pdf
- Data publikacji:
- 2013-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
graph decomposition
vertex colouring
k-connected - Opis:
- 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 \dot\cup ... \dot\cup 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) \le \floor(\frac{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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2013, 33, 2; 347-359
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł