Let G be a multigraph with maximum degree Delta, and let E_1,…,E_n be color classes of a proper edge-coloring of G. A full rainbow matching is a matching containing exactly one edge from each color class. Delcourt–Postle conjecture. If |E_i|≥ Delta+2 for every i, then G has a full rainbow matching. The source later states that both this conjecture and the preceding bipartite conjecture are false, even when the chromatic index equals the maximum degree; consequently this conjecture is refuted.

Delcourt–Postle conjecture on full rainbow matchings in multigraphs

At least 1 year old · documented by 2024

Let $G$ be a multigraph with maximum degree $\Delta$ , and let $E_1,\ldots,E_n$ be color classes of a proper edge-coloring of $G$ . A full rainbow matching is a matching containing exactly one edge from each color class. Delcourt–Postle conjecture. If $|E_i|\geq \Delta+2$ for every $i$ , then $G$ has a full rainbow matching. The source later states that both this conjecture and the preceding bipartite conjecture are false, even when the chromatic index equals the maximum degree; consequently this conjecture is refuted.

References

Primary source

Ronen Wdowinski, “Bounded degree graphs and hypergraphs with no full rainbow matchings”, arXiv:2401.06029 (2025).

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A 2024 paper reports counterexamples that make the conjecture false in infinitely many cases, including cases where the two degree measures agree.

Delcourt and Postle conjectured that sufficiently large color classes in a properly colored multigraph always contain a full rainbow matching.

January 2024 counterexample

The paper Bounded degree graphs and hypergraphs with no full rainbow matchings states that, for every $\Delta \ge 3$ with $\Delta \equiv 0$ or $3 \pmod 4$ , there is a properly edge-colored multigraph with maximum degree and chromatic index $\Delta$ , every color class of size at least $\Delta+2$ , and no full rainbow matching. This directly refutes the conjecture. The report is not independently verified in this scan.

Current status (as of September 2026): The conjecture is reported refuted by the 2024 counterexample, although this automated report does not independently verify the construction.

Sources

No solutions have been posted yet.