← All problems

Positive matching decomposition conjecture for Cartesian products of cycles

4 years old · traced to

Let CmC_m and CnC_n be cycles with m,n≥3m,n\geq3, and let pmd(G)\mathrm{pmd}(G) denote the positive matching decomposition number. Positive matching decomposition conjecture for Cartesian products of cycles.

pmd(Cm□Cn)=6\mathrm{pmd}(C_m\square C_n)=6

for all m,n≥3m,n\geq3 such that m+nm+n is even, or such that (m,n)∈{(3,4),(3,6),(5,6)}(m,n)\in\{(3,4),(3,6),(5,6)\}. The supplied text presents this exact-value assertion after an analysis of positive matchings in the relevant Cartesian products; no resolution beyond that analysis is provided.

References

3 papers in this index state this conjecture (2022–2025). The statement above is taken from the most recent of them; the others are arXiv:2405.20480, arXiv:2202.10463.

Source: Mohammad Farrokhi Derakhshandeh Ghouchan and Ali Akbar Yazdan Pour, “Positive matching decompositions of the cartesian product of graphs”, arXiv:2502.02826 (2025).

Progress summary

Refreshed
Open · progress reported

A reader-submitted preprint claims a small counterexample to the conjecture, but no independent verification was found, so the general question remains unsettled.

Farrokhi Derakhshandeh Ghouchan and Yazdan Pour formulated the conjecture in 2025: the positive matching decomposition number of the relevant cycle products should be 66 in the stated even-parity and exceptional cases.

Known results

  • For all m,n≥3m,n\geq 3, 5≤pmd(Cm□Cn)≤65\leq\mathrm{pmd}(C_m\square C_n)\leq 6.
  • The 2025 paper gives exact value 55 in its stated odd-parity cases and exact value 66 for C3□C3C_3\square C_3 and C4□C4C_4\square C_4.
  • The remaining cases are presented there as Conjecture 4.7.

Community submission (unverified) — November 7, 2026

A submitted proof argues that C3□C4C_3\square C_4 has a five-part positive matching decomposition, hence pmd(C3□C4)=5 \mathrm{pmd}(C_3\square C_4)=5, and claims analogous values for (3,5)(3,5), (3,6)(3,6), and (3,7)(3,7). This would refute the conjecture at several instances, but the submission is not independently assessed.

Current status (as of November 2026): The established bounds and several exact cases remain valid; a submitted counterexample claim is unverified, so the conjecture is not settled.

Sources

Solutions 1

Five positive matchings for C_3 □ C_4: a finite counterexample to Conjecture 4.7 of arXiv:2502.02826See full solutionHide full solution

Result and scope. Farrokhi D. G. and Yazdan Pour, arXiv:2502.02826v1, Conjecture 4.7 (pmd(C_m □ C_n) = 6 for m + n even or (m, n) in {(3,4), (3,6), (5,6)}). False: C_3 □ C_4 has a five-part positive matching decomposition, and pmd(C_3 □ C_4) = 5 exactly; supporting certificates show pmd = 5 also at (3,5), (3,6) and (3,7).

Complete proof: Five positive matchings for C_3 □ C_4: a finite counterexample to Conjecture 4.7 of arXiv:2502.02826 · PDF.

The paper page contains the supplementary proof-source JSON and extract_sources.py. The linked paper supplies the complete argument and states the precise scope of the Lean certificate, ordinary proofs, supporting computations, and source interpretation. Those qualifications are retained here; a supporting computation is not a proof of a broader statement.

This is an AI-assisted research preprint. Internal review is not external journal peer review. Bounded prior-art searches do not establish worldwide priority. See the paper for formalization and trust limits.