Spectral-radius chromatic bound for triangle-free graphs

About 13 years old · traced to

Let GG be a triangle-free graph, let χ(G)\chi(G) denote its chromatic number, and let ρ(G)\rho(G) denote its spectral radius. Spectral-radius chromatic bound. Every triangle-free graph satisfies

χ(G)≤(1+o(1))ρ(G)ln⁡ρ(G).\chi(G)\le(1+o(1))\frac{\rho(G)}{\ln \rho(G)}.

The statement is presented as a possible strengthening of the paper's theorem, moving toward bounds conjectured by Harris; the supplied text gives no resolution of it.

References

Primary source

Anders Martinsson and Raphael Steiner, “Local Shearer bound”, arXiv:2501.00567 (2024).

Additional references

8 papers in this index state this conjecture (2013–2024). The statement above is taken from the most recent of them; the others are arXiv:2408.01709, arXiv:2009.13788, arXiv:1908.10668, arXiv:1809.05260, arXiv:1509.07372, arXiv:1308.1652, arXiv:1305.1139.

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.