On Vizing's problem for triangle-free graphs

Ross J. Kang, Matthieu Rosenfeld

We prove that $\chi (G)\le \lceil (\Delta +1)/2\rceil +1$ for any triangle-free graph $G$ of maximum degree $\Delta$ provided $\Delta \ge 524$. This gives tangible progress towards an old problem of Vi…