Harris's fractional chromatic number conjecture for triangle-free degenerate graphs

From papers

Let GG be a graph, and let dd be a nonnegative integer such that GG is dd-degenerate, meaning that every subgraph of GG has a vertex of degree at most dd. Let \triangle-free mean containing no copy of the triangle, and let χf(G)\chi_f(G) denote the fractional chromatic number of GG. Harris's conjecture. If GG is dd-degenerate and triangle-free, then

χf(G)=O(dlogd).\chi_f(G)=O\left(\frac{d}{\log d}\right).

The conjecture predicts a logarithmic improvement over the general degeneracy bound for fractional chromatic number; the paper presents results toward it and later states that it has been resolved, so the conjecture itself is no longer open.

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

Anders Martinsson, “Triangle-free d-degenerate graphs have small fractional chromatic number”, arXiv:2501.18238 (2025).

Additional references

2 papers in this index state this conjecture (2018–2025). The statement above is taken from the most recent of them; the others are arXiv:1811.11116.

Solutions 0

No solutions have been posted yet.