Balanced k-decompositions of graphs
Journal
Discrete Applied Mathematics
Journal Volume
160
Journal Issue
10-11
Pages
1639-1642
Date Issued
2012
Author(s)
Abstract
For a given integer k<2, a balanced k-coloring of a graph G is a mapping cV(G)→0,1,2,...,k such that | Aj|=|A j′| for 1≤j< j′≤k, where Aj=v∈V(G)c(v)=j for 0≤j≤k. The balanced k-decomposition number fk(G) of G is the minimum integer s with the property that for any balanced k-coloring c there is a partition V(G)= V1∪ V2∪⋯∪ Vr such that Vi induces a connected subgraph with | Vi|≤s and | Vi∩ Aj|=| Vi∩Aj′| for 1≤i≤r and 1≤j< j′≤k. In this paper, we determine fk(G) for some graphs of high connectivity, trees and complete multipartite graphs. © 2012 Elsevier Ltd. All rights reserved.
Type
journal article