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

About 7 years old · traced to

Let GG be a graph, let nn and mm be integers with m≤nm\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,n−1)=n−1.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=n−1m=n-1. The source gives no resolution evidence for this assertion.

References

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.