On Independent Sets in Graphs with Given Minimum Degree

DOI10.1017/S0963548313000369zbMath1282.05181arXiv1210.1497OpenAlexW2964191445MaRDI QIDQ5397737

Hiu-Fai Law, Colin J. H. McDiarmid

Publication date: 24 February 2014

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1210.1497

zbMATH Keywords

largest random independent sets

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Vertex degrees (05C07)

Related Items (4)

The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree ⋮ Maximizing the Number of Independent Sets of a Fixed Size ⋮ Many cliques with few edges and bounded maximum degree ⋮ Extremal H‐Colorings of Graphs with Fixed Minimum Degree

Cites Work

• Two problems on independent sets in graphs
• Matchings and independent sets of a fixed size in regular graphs
• Random planar graphs
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• The Number of Independent Sets in a Regular Graph

This page was built for publication: On Independent Sets in Graphs with Given Minimum Degree