Degree-bounded bipartite rainbow matching conjecture

About 10 years old · traced to

Let d>1d>1, and let F1,…,FkF_1,\ldots,F_k be bipartite graphs on a common vertex set. Write Δ(Fi)\Delta(F_i) for the maximum vertex degree of FiF_i, and call a choice of pairwise vertex-disjoint edges ei∈Fie_i\in F_i a rainbow matching.

Degree-bounded bipartite rainbow matching conjecture. If

Δ(Fi)≤dand∣Fi∣>(k−1)d\Delta(F_i)\leq d\quad\text{and}\quad |F_i|>(k-1)d

for every ii, then the system F1,…,FkF_1,\ldots,F_k has a rainbow matching.

The source notes that the analogous assertion fails for d=1d=1, while suggesting that the degree bound d>1d>1 should suffice. No resolution is supplied in the source.

References

Primary source

Ron Aharoni and David Howard, “A rainbow r-partite version of the Erdős-Ko-Rado theorem”, arXiv:1605.06752 (2016).

Additional references

2 papers in this index state this conjecture (2016). The statement above is taken from the most recent of them; the others are arXiv:1605.05667.

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.