← All problems

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

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