19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

Balanced decomposition number of 2-connected graphs

Presented by Dr. Narayanan NARAYANAN
Type: Oral presentation
Track: Coloring of Graphs


We prove a conjecture due to Fujita et al. which states that the balanced decomposition number of any 2-connected graph is at most $\lfloor n/2 \rfloor +1$. We use the structural properties of minimally 2-connected graph. \def\fnbt{{\lfloor n/2 \rfloor}} A {\em balanced colouring} of $G$ is a partition $c:V\mapsto \{+1,0,-1\}$ such that $\sum_{v\in V}c(v)=0$. Let $R=\{x:c(x)=+1;x\in V$ and $B=\{x|c(x)=-1;x\in V$. The elements of $R$ and $B$ are respectively called {\em red} and {\em blue} vertices. When $|R|=|B|=r$, we say that $G$ has a {\em balanced $r$-colouring}. A subset of $V$ is {\em balanced} if the number of red and blue vertices are the same. Given a balanced colouring, a {\em balanced decomposition} is a partition $V=V_1\cup V_2 \ldots \cup V_k$ such that each $V_i, 1\le i\le k$ is balanced and $G[V_i]$ is connected. The {\em size} of a decomposition is maximum of $|V_i|,1\le i \le k$. For a connected graph, define $f(t,G) = \min \{i\in \mathbb{N}:$ for everybalanced $t$-colouring, $G$ has a balanced decomposition of size at most $i\}$. The {\em balanced colouring number} of a graph $G$ is defined as $f(G) = \max \{f(t,G):0\le t \le \fnbt\}$.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors