Randomly finding independent sets in locally sparse graphs

DOI10.1007/s10878-022-00948-wOpenAlexW4309637798MaRDI QIDQ2099383

Ye Wang, Yan Li

Publication date: 23 November 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-022-00948-w

zbMATH Keywords

independence numberlocal sparseness\((k, m)\)-colorable

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Density (toughness, etc.) (05C42)

Cites Work

• Unnamed Item
• Lower bounds for independence numbers of some locally sparse graphs
• An upper bound on the Ramsey numbers R(3,k)
• A note on the independence number of triangle-free graphs
• A note on Ramsey numbers
• The independence number of graphs with a forbidden cycle and Ramsey numbers
• Lower bounds for small diagonal Ramsey numbers
• On book-complete graph Ramsey numbers
• The independence numbers of weighted graphs with forbidden cycles
• On cycle—Complete graph ramsey numbers
• Independence numbers of locally sparse graphs and a Ramsey type problem
• Asymptotic upper bounds for Ramsey functions

This page was built for publication: Randomly finding independent sets in locally sparse graphs