The bounded fractional-chromatic-number-to-Hall-ratio conjecture
The bounded fractional-chromatic-number-to-Hall-ratio conjecture
Let be a graph. Its fractional chromatic number is
where is the maximum weight of an independent set and . Its Hall ratio is
The bounded fractional-chromatic-number-to-Hall-ratio conjecture. There is an absolute constant such that, for every graph ,
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
Sign in to submit a solution.
No solutions have been posted yet.