Conjecture on fractional chromatic number versus edges in triangle-free graphs

At least 7 years old · documented by

Let GG be a triangle-free graph with mm edges, and let χf(G)\chi_f(G) denote its fractional chromatic number. Edge-based fractional chromatic-number conjecture. As m→∞m\to\infty, every such graph satisfies

χf(G)≤(24/3+o(1))m1/3/(log⁡m)2/3.\chi_f(G)\leq (2^{4/3}+o(1))m^{1/3}/(\log m)^{2/3}.

The conjecture is presented as an analogue of Shearer's bound, giving a sharper fractional colouring prediction in terms of the number of edges.

References

Primary source

Wouter Cames van Batenburg, Rémi de Joannis de Verclos, Ross J. Kang and François Pirot, “Bipartite induced density in triangle-free graphs”, arXiv:1808.02512 (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.