On the balanced decomposition number

DOI10.1007/S00373-015-1526-5zbMATH Open1327.05280arXiv1212.2308OpenAlexW1964083083MaRDI QIDQ897290FDOQ897290

Authors: Tadashi Sakuma 

Publication date: 17 December 2015

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: A {em 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}uplus{P}_{2}uplusX$ and $|P_1|=|P_2|$. A {em balanced decomposition} associated with the balanced coloring $V(G)=P_{1}uplus{P}_{2}uplusX$ of $G$ is defined as a partition of $V(G)=V_{1}upluscdotsuplus{V}_r$ (for some $r$) such that, for every $iin1,cdots,r$, the subgraph $G[V_i]$ of $G$ is connected and $|V_{i}cap{P}_1|=|V_{i}cap{P}_2|$. 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)=P_{1}uplus{P}_{2}uplusX$ of $G$, there exists a balanced decomposition $V(G)=V_{1}upluscdotsuplus{V}_r$ whose every element $V_i(i=1,cdots,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 $lfloorfrac|V(G)|2floor$-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.

Full work available at URL: https://arxiv.org/abs/1212.2308

Recommendations

• Graphs with small balanced decomposition numbers
• Further results on the balanced decomposition number
• On a conjecture on the balanced decomposition number
• The balanced decomposition number and vertex connectivity
• The balanced decomposition number of \({TK}_4\) and series-parallel graphs

zbMATH Keywords

connectivitygraph decompositioncoloringbipartite matching

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Graph theory
• On Representatives of Subsets
• Balanced decomposition of a vertex-colored graph
• The Balanced Decomposition Number and Vertex Connectivity
• On a conjecture on the balanced decomposition number

Cited In (3)

• Combinatorics of balanced carries
• Balanced decomposition of a vertex-colored graph
• Title not available (Why is that?)

This page was built for publication: On the balanced decomposition number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q897290)