The exceptional-line-graph 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. Exceptional-line-graph conjecture. If GG is the line graph of a graph and is not a graph as in Example, then

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

The source explains that the excluded construction is an obstruction to the stronger bipartite statement and that this conjecture would imply the general-graph full-matching conjecture.

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.