2012/12/11 by Tadashi Sakuma, Sakuma, Tadashi
Computer Science · Mathematics · Social Sciences · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Japanese History and Culture
paper · pdf · doi:10.48550/arxiv.1212.2308
A \em balanced coloring of a graph G means a triple \P1,P2,X\ of mutually disjoint subsets of the vertex-set V(G) such that V(G)=P1 \uplus P2 \uplus X and |P1|=|P2|. A \em balanced decomposition associated with the balanced coloring V(G)=P1 \uplus P2 \uplus X of G is defined as a partition of V(G)=V1 \uplus ⋯ \uplus Vr (for some r) such that, for every i ∈ \1,⋯,r\, the subgraph G[Vi] of G is connected and |Vi ∩ P1| = |Vi ∩ P2|. Then the \em balanced decomposition number of a graph G is defined as the minimum integer s such that, for every balanced coloring V(G)=P1 \uplus P2 \uplus X of G, there exists a balanced decomposition V(G)=V1 \uplus ⋯ \uplus Vr whose every element Vi (i=1, ⋯, r) has at most s vertices. S. Fujita and H. Liu [\/SIAM J. Discrete Math. 24, (2010), pp. 1597--1616\/] proved a nice theorem which states that the balanced decomposition number of a graph G is at most 3 if and only if G is \lfloor(|V(G)|)/(2)\rfloor-connected. Unfortunately, their proof is lengthy (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.