Independent sets and repeated degrees (Q1363652)

\textit{P. Erdös}, \textit{S. Fajtlowicz} and \textit{W. Staton} [Discrete Math. 92, No. 1-3, 85-88 (1991; Zbl 0752.05028)] showed that every triangle-free graph of order \(n\) in which no degree is repeated more than twice is bipartite and thus has independence number at least \(n/2\). \textit{P. Erdös}, \textit{R. Faudree}, \textit{T. J. Reid}, \textit{R. Schelp} and \textit{W. Staton} [Discrete Math. 141, No. 1-3, 275-290 (1995; Zbl 0833.05074)] asked for triangle-free graphs of arbitrarily large order with no degree repeated more than \(k\) times and having independence number \((1+o(1))n/k\); they showed the existence of such graphs for \(k=4\) also. Here the authors give a probabilistic proof of the existence of such graphs for all \(k\geq 2\). They close with several interesting questions and a conjecture.