Lower bounds for constant degree independent sets

DOI10.1016/0012-365X(92)00463-2zbMATH Open0799.05031MaRDI QIDQ1322210FDOQ1322210

Authors: Michael O. Albertson, Debra L. Boutin 

Publication date: 8 November 1994

Published in: Discrete Mathematics (Search for Journal in Brave)

Recommendations

• A lower bound on independence in terms of degrees
• Independent sets near the lower bound in bounded degree graphs
• scientific article; zbMATH DE number 866059
• A lower bound on the independence number of a graph in terms of degrees
• Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees
• Independent sets in bounded-degree hypergraphs
• Independent Sets in Bounded-Degree Hypergraphs
• Maximum independent sets in graphs of low degree
• A lower bound on the independence number of a graph
• A lower bound on the independence number of arbitrary hypergraphs

zbMATH Keywords

treeboundsindependent setplanar graphdegree

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cites Work

• Graph theory
• Title not available (Why is that?)
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Lower bounds on the independence number in terms of the degrees
• Title not available (Why is that?)
• People Who Know People

Cited In (8)

• Regular independent sets
• Equating \(\kappa\) maximum degrees in graphs without short cycles
• Equating two maximum degrees
• Title not available (Why is that?)
• Bounded-degree independent sets in planar graphs
• Irregular independence and irregular domination
• Independence numbers of polyhedral graphs
• Title not available (Why is that?)

This page was built for publication: Lower bounds for constant degree independent sets

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