On the Balanced Decomposition Number

• Published in: Graphs and combinatorics 2015-11, Vol.31 (6), p.2377-2380
• Main Author: Sakuma, Tadashi
• Format: Article
• Language: English
• Subjects: Combinatorics; Engineering Design; Mathematics; Mathematics and Statistics; Original Paper
• ISSN: 0911-0119; 1435-5914
• DOI: 10.1007/s00373-015-1526-5

A balanced coloring of a graph G means a triple { P 1 , P 2 , X } of mutually disjoint subsets of the vertex-set V ( G ) such that V ( G ) = P 1 ∪ ˙ P 2 ∪ ˙ X and | P 1 | = | P 2 | . A balanced decomposition associated with the balanced coloring V ( G ) = P 1 ∪ ˙ P 2 ∪ ˙ X of G is defined as a partition of V ( G ) = V 1 ∪ ˙ ⋯ ∪ ˙ V r (for some r ) such that, for every i ∈ { 1 , … , r } , the subgraph G [ V i ] of G is connected and | V i ∩ P 1 | = | V i ∩ P 2 | . Then the balanced decomposition number of a graph G is defined as the minimum integer s such that, for every balanced coloring V ( G ) = P 1 ∪ ˙ P 2 ∪ ˙ X of G , there exists a balanced decomposition V ( G ) = V 1 ∪ ˙ ⋯ ∪ ˙ V r such that every element V i ( i = 1 , … , r ) has at most s vertices. Fujita and Liu (SIAM J Discret Math 24:1597–1616, 2010 ) proved an interesting theorem which states that the balanced decomposition number of a graph G is at most 3 if and only if G is ⌊ | V ( G ) | 2 ⌋ -connected. Unfortunately, their proof is long (about 10 pages) and complicated. Here we give an immediate proof of the theorem. This proof makes clear a relationship between balanced decomposition number and graph matching.