Fixed-size independent-set conjecture for chromatic graphs with connectivity below chromaticity
Fixed-size independent-set conjecture for chromatic graphs with connectivity below chromaticity
Let be an -vertex -chromatic -connected graph, and let denote the number of independent sets of size in . Fixed-size independent-set conjecture. If , , and , then
This proposes that the same extremal behavior for the number of independent sets of size should persist when the chromatic number exceeds the connectivity; the source presents it as an open question.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
John Engbers, Lauren Keough and Taylor Short, “Independent Sets in n-vertex k-chromatic, -connected graphs”, arXiv:1907.03913 (2019).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.