A tight chromatic bound in terms of triangle count and local triangle bound

From papers

Let GG be a graph with nn vertices, tt triangles, and local triangle bound yy. Here, the local triangle bound yy is an upper bound on the number of triangles containing any given vertex. The conjectured tight bound. One should have

χ(G)t1/3log2/3(t2/y3)+nlogn.\chi(G) \lesssim \frac{t^{1/3}}{\log^{2/3}(t^2/y^3)}+\sqrt{\frac{n}{\log n}}.

This would strengthen the stated theorem, imply the proposition there as the special case tnyt\leq ny, and match the given lower bound; its status is 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

David G. Harris, “Some results on chromatic number as a function of triangle count”, arXiv:1604.00438 (2019).

Solutions 0

No solutions have been posted yet.