A new lower bound for the number of conjugacy classes

In 2003, Héthelyi and Külshammer proposed that if $G$ is a finite group and $p$ is a prime dividing the group order, then $k(G)\ge 2\sqrt{p-1}$, and they proved this conjecture for solvable $G$ and showed that it is sharp for those primes $p$ for which $\sqrt{p-1}$ is an integer. This initiated a flurry of activity, leading to many generalizations and variations of the result; in particular, today the conjecture is known to be true for all finite groups. In this note, we put forward a natural new and stronger conjecture, which is sharp for all primes $p$, and we prove it for solvable groups, and when $p$ is large, also for arbitrary groups.