Aharoni–Barat–Wanless rainbow matching conjecture

Let GG be a bipartite graph, let Δ(G)\Delta(G) denote its maximum degree, and suppose that every colour is used on more than Δ(G)+1\Delta(G)+1 edges. A rainbow matching is a matching whose edges have pairwise distinct colours.

Aharoni–Barat–Wanless conjecture. The graph GG has a rainbow matching using every colour.

This is another conjecture about rainbow subgraphs. It is disproved by the construction in the paper, which supplies a counterexample satisfying the relevant edge-colour multiplicity condition.

Sources & referencesView supporting material

Primary source

Alexey Pokrovskiy and Benny Sudakov, “A counterexample to Stein's Equi-n-square Conjecture”, arXiv:1711.00429 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.