Degree multiplicities and independent sets in \(K_ 4\)-free graphs (Q1815307): Difference between revisions

The main result of this paper states that there is a sequence \((G_n)^\infty_{n=1}\) of graphs such that every graph \(G_n\) has \(n\) vertices, does not contain any complete subgraph with four vertices, has at most five vertices of the same degree and its independence number is \(o(n)\). This is a partial solution of a problem suggested by \textit{P. Erdös}, \textit{R. J. Faudree}, \textit{T. J. Reid}, \textit{R. Schelp} and \textit{W. Staton} [Discrete Math. 141, No. 1-3, 275-290 (1995; Zbl 0833.05074)].