Aharoni–Briggs–Kim–Kim conjecture for graphs of maximum degree two

Let GG be a graph, let nn and mm be integers with mnm\le n, and let fG(n,m)f_G(n,m) denote the minimum number of independent nn-sets whose collection has a rainbow independent mm-set. Let D(2)\mathcal{D}(2) be the family of graphs with maximum degree at most two. Aharoni–Briggs–Kim–Kim conjecture.

fD(2)(n,n1)=n1.f_{\mathcal{D}(2)}(n,n-1)=n-1.

This asserts that the general lower bound fG(n,m)mf_G(n,m)\ge m is tight for graphs of maximum degree at most two when m=n1m=n-1. The source gives no resolution evidence for this assertion.

Sources & referencesView supporting material

Primary source

Yue Ma, Xinmin Hou, Jun Gao, Boyuan Liu and Zhi Yin, “Rainbow independent sets in graphs with maximum degree two”, arXiv:2108.02520 (2021).

Additional references

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

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.