Fixed-size independent-set conjecture for highly connected chromatic graphs

At least 6 years old · documented by

Let GG be an nn-vertex kk-chromatic ℓ\ell-connected graph, and let it(G)i_t(G) denote the number of independent sets of size tt in GG. Fixed-size independent-set conjecture. If 3≤k≤ℓ3 \leq k \leq \ell, n≥2ℓn \geq 2\ell, and t≥3t \geq 3, then

it(G)≤it(G∗).i_t(G) \leq i_t(G^*).

This would extend the paper's result for sufficiently large independent sets to all sizes t≥3t \geq 3 under the stated parameter conditions; the conjecture is presented as an open question.

References

Primary source

John Engbers, Lauren Keough and Taylor Short, “Independent Sets in n-vertex k-chromatic, -connected graphs”, arXiv:1907.03913 (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.