Lower bounds on the independence number in terms of the degrees

DOI10.1016/0095-8956(83)90003-5zbMath0505.05037OpenAlexW1976890066MaRDI 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 graphfinding large independent sets

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items

Large induced degenerate subgraphs ⋮ New bounds on the independence number of connected graphs ⋮ The largest transversal numbers of uniform hypergraphs ⋮ Edge density and independence ratio in triangle-free graphs with maximum degree three ⋮ On the \(k\)-residue of disjoint unions of graphs with applications to \(k\)-independence ⋮ On vertex independence number of uniform hypergraphs ⋮ New bounds for contagious sets ⋮ Embedding bipartite distance graphs under Hamming metric in finite fields ⋮ Partitions of graphs into small and large sets ⋮ Lower bounds on the stability number of graphs computed in terms of degrees ⋮ An improved lower bound on the independence number of a graph ⋮ Computing independent sets in graphs with large girth ⋮ A note on the independence number of triangle-free graphs. II ⋮ Independent sets in graphs ⋮ Recoverable Values for Independent Sets ⋮ Greed is good: Approximating independent sets in sparse and bounded-degree graphs ⋮ RECOGNIZING BY ORDER AND DEGREE PATTERN OF SOME PROJECTIVE SPECIAL LINEAR GROUPS ⋮ The potential of greed for independence ⋮ On sequential heuristic methods for the maximum independent set problem ⋮ New potential functions for greedy independence and coloring ⋮ Bounding the feedback vertex number of digraphs in terms of vertex degrees ⋮ A note on the greedy algorithm for finding independent sets of \(C_k\)-free graphs ⋮ The \(k\)-regular induced subgraph problem ⋮ Simple and local independent set approximation ⋮ GreedyMAX-type Algorithms for the Maximum Independent Set Problem ⋮ MAX for \(k\)-independence in multigraphs ⋮ Ramsey numbers and an approximation algorithm for the vertex cover problem ⋮ On the maximum independent set problem in graphs of bounded maximum degree ⋮ An upper bound on the Ramsey numbers R(3,k) ⋮ Extending the MAX algorithm for maximum independent set ⋮ New sufficient conditions for \(\alpha\)-redundant vertices ⋮ A note on greedy algorithms for the maximum weighted independent set problem ⋮ The maximum clique problem ⋮ Lower bounds for constant degree independent sets ⋮ Independence and the Havel-Hakimi residue ⋮ Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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