Independent sets and repeated degrees

DOI10.1016/0012-365X(95)00355-ZMaRDI QIDQ1363652zbMATH OpenOpenAlexFDO

Authors Béla Bollobás, Alex Scott

Publication date 16 February 1998

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

independence numberindependent setsrepeated degreestriangle-free graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (05C99)

Review text

\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.

Recommendations

• Triangle-free regular graphs
• Size and independence in triangle‐free graphs with maximum degree three
• A note on the independence number of triangle-free graphs. II
• On the tightness of the \(\frac {5}{14}\) independence ratio

Cites work

• Degree sequence and independence in K(4)-free graphs
• Degree sequences in triangle-free graphs

Cited in

(14)

• Triangle-free regular graphs
• Independent sets and second category
• Degree multiplicities and independent sets in \(K_ 4\)-free graphs
• Degree sequence and independence in K(4)-free graphs
• Equating maximum degrees in graphs without short cycles
• Large induced subgraphs with three repeated degrees
• scientific article; zbMATH DE number 3941572 (Why is no real title available?)
• scientific article; zbMATH DE number 140115 (Why is no real title available?)
• Forcing k-repetitions in degree sequences
• Large induced subgraphs with \(k\) vertices of almost maximum degree
• Equating two maximum degrees
• scientific article; zbMATH DE number 845597 (Why is no real title available?)
• Equating three degrees of graphs
• Large induced subgraphs with equated maximum degree

This page was built for publication: Independent sets and repeated degrees

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