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

About 10 years old · traced to

Let GG be a graph. Its fractional chromatic number is

χf(G)=sup⁡w:V→R+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)=∑v∈Vw(v)w(V)=\sum_{v\in V}w(v). Its Hall ratio is

ρ(G)=sup⁡U⊆V∣U∣α(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.

References

Primary source

David G. Harris, “Some results on chromatic number as a function of triangle count”, arXiv:1604.00438 (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.