The maximum-degree-two rainbow matching conjecture

Let fG(n,m)f_G(n,m) denote the least number of independent nn-sets in a graph GG that guarantees a rainbow independent set of size mm. Maximum-degree-two conjecture. If GG has maximum degree 22, then

fG(n,n1)=n1.f_G(n,n-1)=n-1.

Equivalently, every n1n-1 matchings of size nn in a graph of maximum degree 22 have a full rainbow matching. The source identifies this as a special case of the exceptional-line-graph conjecture and notes that the one-cycle case follows from the chordal-graph theorem.

Sources & referencesView supporting material

Primary source

Ron Aharoni, Joseph Briggs, Jinha Kim and Minki Kim, “Rainbow independent sets in certain classes of graphs”, arXiv:1909.13143 (2019).

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.