Graphs with small balanced decomposition numbers
Journal
Journal of Combinatorial Optimization
Journal Volume
28
Journal Issue
2
Pages
505-510
Date Issued
2014
Author(s)
Abstract
A balanced coloring of a graph G is an ordered pair (R,B) of disjoint subsets R,B ⊆ V(G) with |R|=|B|. The balanced decomposition number f(G)of a connected graph G is the minimum integer f such that for any balanced coloring (R,B)of G there is a partition P of V(G) such that S induces a connected subgraph with |S| ≤ f and |S ∩ R| = |S ∩ B| for in P. This paper gives a short proof for the result by Fujita and Liu (2010) that a graph G of n vertices has f(G)=3if and only if G is ⌊n/2⌋-connected but is not a complete graph. © 2012 Springer Science+Business Media New York.
Type
journal article