Harris's conjecture on the Hall ratio and fractional chromatic number
Let be a graph, let denote its fractional chromatic number, and let denote its Hall ratio, the maximum of over all non-null subgraphs . Harris's Hall-ratio conjecture. There exists a constant such that
for every graph . The conjecture proposed a universal constant-factor upper bound on the fractional chromatic number in terms of the Hall ratio, but the paper's constructions refute it by producing graphs for which the ratio is unbounded.
References
- Adam Blumenthal, Bernard Lidicky, Ryan R. Martin, Sergey Norin, Florian Pfender and Jan Volec, “Counterexamples to a conjecture of Harris on Hall ratio”, arXiv:1811.11116 (2020).
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.