Lower bounds on the independence number in terms of the degrees

DOI10.1016/0095-8956(83)90003-5zbMath0505.05037MaRDI QIDQ1835927

Jerrold R. Griggs

Publication date: 1983

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(83)90003-5

zbMATH Keywords

connected triangle-free graph; finding large independent sets

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

68R10: Graph theory (including graph drawing) in computer science

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

Related Items

Bounding the feedback vertex number of digraphs in terms of vertex degrees, Greed is good: Approximating independent sets in sparse and bounded-degree graphs, Ramsey numbers and an approximation algorithm for the vertex cover problem, An upper bound on the Ramsey numbers R(3,k), A note on the greedy algorithm for finding independent sets of \(C_k\)-free graphs, Large induced degenerate subgraphs, Lower bounds on the stability number of graphs computed in terms of degrees, Computing independent sets in graphs with large girth, A note on the independence number of triangle-free graphs. II, The maximum clique problem, Lower bounds for constant degree independent sets, Independence and the Havel-Hakimi residue, A note on greedy algorithms for the maximum weighted independent set problem, The largest transversal numbers of uniform hypergraphs, Edge density and independence ratio in triangle-free graphs with maximum degree three, Recoverable Values for Independent Sets, GreedyMAX-type Algorithms for the Maximum Independent Set Problem

Cites Work

• An upper bound on the Ramsey numbers R(3,k)
• A proof of an inequality of Marcus and Lopes
• A note on Ramsey numbers
• Approximation algorithms for combinatorial problems
• Some Ramsey-Type Numbers and the Independence Ratio
• On the independence ratio of a graph
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item