Martinsson–Steiner conjecture on the fractional chromatic number of degenerate triangle-free graphs

Less than 1 year old · traced to

Let dd be sufficiently large, and let GG be a dd-degenerate triangle-free graph with fractional chromatic number χf(G)\chi_f(G). Martinsson–Steiner conjecture. The following two assertions hold:

  1. For every such graph GG,
χf(G)≤(1+o(1))dlog⁡d.\chi_f(G)\leq(1+o(1))\frac{d}{\log d}.
  1. There exists a triangle-free dd-degenerate graph GG such that
χf(G)≥(1−o(1))dlog⁡d.\chi_f(G)\geq(1-o(1))\frac{d}{\log d}.

The upper-bound part sharpens the proved bound of Martinsson and Steiner, while the lower-bound part asserts its asymptotic sharpness. The source gives no resolution of this two-part conjecture.

References

Primary source

Peter Allen, Abhishek Dhawan and Jonathan A. Noel, “Sharp bounds for the fractional chromatic number of high-girth d-degenerate graphs”, arXiv:2607.26271 (2026).

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.