2025/02/05 by Mohammad Farrokhi Derakhshandeh Ghouchan, Ghouchan, Mohammad Farrokhi Derakhshandeh, Ali Akbar Yazdan Pour +1
Computer Science · #Graph Theory and Algorithms #Graph Labeling and Dimension Problems #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2502.02826
Let Γ=(V,E) be a finite simple graph. A matching M ⊆ 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 Γ with p parts is an ordered partition E1,…,Ep of E such that Ei is a positive matching of (V, E ∖ \bigcupj=1i-1 Ej), for i = 1, …, p. The smallest p for which Γ admits a pmd with p parts is denoted by pmd(Γ). 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.