Degree multiplicities and independent sets in \(K_ 4\)-free graphs (Q1815307)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Degree multiplicities and independent sets in \(K_ 4\)-free graphs |
scientific article |
Statements
Degree multiplicities and independent sets in \(K_ 4\)-free graphs (English)
0 references
7 November 1996
0 references
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)].
0 references
degree
0 references
independence number
0 references
0 references