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

About 10 years old · traced to

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/3log⁡2/3(t2/y3)+nlog⁡n.\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 t≤nyt\leq ny, and match the given lower bound; its status is open.

References

Primary source

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

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.