The bounded fractional-chromatic-number-to-Hall-ratio conjecture

From papers

Let GG be a graph. Its fractional chromatic number is

χf(G)=supw:VR+w(V)α(G,w),\chi_{\mathrm{f}}(G)=\sup_{w:V\to\mathbf R_{+}}\frac{w(V)}{\alpha(G,w)},

where α(G,w)\alpha(G,w) is the maximum weight of an independent set and w(V)=vVw(v)w(V)=\sum_{v\in V}w(v). Its Hall ratio is

ρ(G)=supUVUα(G[U]).\rho(G)=\sup_{U\subseteq V}\frac{|U|}{\alpha(G[U])}.

The bounded fractional-chromatic-number-to-Hall-ratio conjecture. There is an absolute constant such that, for every graph GG,

χf(G)O(ρ(G)).\chi_{\mathrm{f}}(G)\leq O(\rho(G)).

This is presented as the opposite of Johnson's conjecture, which concerned whether the ratio could be unbounded; it is open in the source.

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

David G. Harris, “Some results on chromatic number as a function of triangle count”, arXiv:1604.00438 (2019).

Solutions 0

No solutions have been posted yet.