Positive matching decompositions of the cartesian product of graphs

Abstract

Let $\Gamma =(V,E)$ be a finite simple graph. A matching $M\subseteq E$ is positive if there exists a weight function on $V$ such that the matching $M$ is characterized by those edges with positive weights. A positive matching decomposition (pmd) of $\Gamma$ with $p$ parts is an ordered partition $E_1,\dots ,E_p$ of $E$ such that $E_i$ is a positive matching of $(V,E\setminus {\bigcup }_{j=1}^{i-1}{E}_j)$, for $i=1,\dots ,p$. The smallest $p$ for which $\Gamma$ admits a pmd with $p$ parts is denoted by $\mathrm{pmd}(\Gamma )$. We study the pmd of the Cartesian product of graphs and give sharp upper bounds for them in terms of the pmds and chromatic numbers of their components. In special cases, we compute the pmd of grid graphs that is the Cartesian product of paths and cycles.

23 pages, 7 figures