Degree multiplicities and independent sets in K_ 4-free graphs

DOI10.1016/0012-365X(95)00002-EMaRDI QIDQ1815307zbMATH OpenOpenAlexFDO

Authors Béla Bollobás

Publication date 7 November 1996

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(95)00002-e

zbMATH Keywords

degreeindependence number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

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)].

Recommendations

• Degree sequence and independence in K(4)-free graphs
• Independent sets and repeated degrees
• Finding independent sets in \(K_4\)-free 4-regular connected graphs
• The independence number in graphs of maximum degree three
• Lower bounds on size and independence inK4-free graphs

Cites work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Degree sequences in triangle-free graphs
• Graph Theory and Probability
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 3435529 (Why is no real title available?)
• scientific article; zbMATH DE number 3333194 (Why is no real title available?)
• On a Ramsey-Turán type problem

Cited in

(10)

• On independent generalized degrees and independence numbers in \(K(1,m)\)- free graphs
• Degree sequence and independence in K(4)-free graphs
• Independent sets in \((P_4+P_4\),triangle)-free graphs
• Large induced subgraphs with three repeated degrees
• Forcing k-repetitions in degree sequences
• Lower bounds on size and independence inK4-free graphs
• Equating two maximum degrees
• Further Improvement on Maximum Independent Set in Degree-4 Graphs
• Equating three degrees of graphs
• Large induced subgraphs with equated maximum degree

This page was built for publication: Degree multiplicities and independent sets in \(K_ 4\)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1815307)