Degree multiplicities and independent sets in \(K_ 4\)-free graphs
type: Item
instance of: scholarly article
title: Degree multiplicities and independent sets in \(K_ 4\)-free graphs
zbMATH Open document ID: 0858.05056
DOI: 10.1016/0012-365X(95)00002-E
author: Béla Bollobás
published in: Discrete Mathematics
publication date: 1996-11-07T00:00:00Z
review text: 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)].
reviewed by: Bohdan Zelinka
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 943216
zbMATH Keywords: degree
zbMATH Keywords: independence number
MaRDI profile type: Publication
cites work: A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
cites work: Q3682518
cites work: On a Ramsey-Turán type problem
cites work: Graph Theory and Probability
cites work: Degree sequences in triangle-free graphs
cites work: Q5610920
cites work: Q4401979
full work available at URL: 0012-365x(95)00002-e
OpenAlex ID: W2147283108
description: scientific article; zbMATH DE number 943216