On the Balanced Decomposition Number
On the Balanced Decomposition Number
复制标题
关于平衡分解数
DOI：
10.1007/s00373-015-1526-5
复制
发表时间：
2015
影响因子：
0.7
通讯作者：
Tadashi SAKUMA
中科院分区：
文献类型：
--
作者：
Tadashi SAKUMA
图的平衡着色是指顶点集的三个互不相交的子集，使得和。的平衡染色的平衡分解被定义为（对于某些）的一个划分，使得对于每一个，的子图是连通的。则图的平衡分解数被定义为最小整数，使得对于图的每一个平衡着色，都存在一个平衡分解，使得每个元素在最多个顶点上。Fujita和Liu（SIAM J Discret Math 24：1597 - 1616，2010）证明了一个有趣的定理，该定理指出一个图的平衡分解数在最多且仅为ifis-连通的。不幸的是，他们的证明很长（大约10页），而且很复杂。这里我们给出定理的一个直接证明。证明了平衡分解数与图匹配之间的关系。
Abalanced coloringof a graphmeans a tripleof mutually disjoint subsets of the vertex-setsuch thatand. Abalanced decompositionassociated with the balanced coloringofis defined as a partition of(for some) such that, for every, the subgraphofis connected and. Then thebalanced decomposition numberof a graphis defined as the minimum integersuch that, for every balanced coloringof, there exists a balanced decompositionsuch that every elementhas at mostvertices. Fujita and Liu (SIAM J Discret Math 24:1597–1616, 2010) proved an interesting theorem which states that the balanced decomposition number of a graphis at mostif and only ifis-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.