Fixed-size independent-set conjecture for chromatic graphs with connectivity below chromaticity

About 7 years old · traced to

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 k≥4k \geq 4, k>ℓk>\ell, and t≥3t \geq 3, then

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

This proposes that the same extremal behavior for the number of independent sets of size tt should persist when the chromatic number exceeds the connectivity; the source presents it 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.