On the balanced decomposition number

DOI10.1007/S00373-015-1526-5MaRDI QIDQ897290zbMATH OpenOpenAlexFDO

Authors Tadashi Sakuma

Publication date 17 December 2015

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

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

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)

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.

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

Cites work

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

Cited in

(9)

• Combinatorics of balanced carries
• Balanced decomposition of a vertex-colored graph
• scientific article; zbMATH DE number 5171545 (Why is no real title available?)
• Balanced \(k\)-decompositions of graphs
• The balanced decomposition number and vertex connectivity
• Further results on the balanced decomposition number
• Graphs with small balanced decomposition numbers
• The balanced decomposition number of \({TK}_4\) and series-parallel graphs
• On a conjecture on the balanced decomposition number

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)