Harris's conjecture on the Hall ratio and fractional chromatic number

From papers

Let GG be a graph, let χf(G)\chi_f(G) denote its fractional chromatic number, and let ρ(G)\rho(G) denote its Hall ratio, the maximum of v(H)/α(H)v(H)/\alpha(H) over all non-null subgraphs HGH\subseteq G. Harris's Hall-ratio conjecture. There exists a constant CC such that

χf(G)Cρ(G)\chi_f(G)\le C\cdot\rho(G)

for every graph GG. 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 χf(G)/ρ(G)\chi_f(G)/\rho(G) is unbounded.

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

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).

Solutions 0

No solutions have been posted yet.