Lower bounds for independence numbers of some locally sparse graphs

DOI10.1007/S10878-012-9578-4MaRDI QIDQ489716zbMATH OpenOpenAlexFDO

Authors Yusheng Li, Qizhong Lin

Publication date 21 January 2015

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

Full work available at URL https://doi.org/10.1007/s10878-012-9578-4

zbMATH Keywords

independence numberlocally distinct coloringlocally sparse graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Programming involving graphs or networks (90C35)

Recommendations

• Randomly finding independent sets in locally sparse graphs
• Independence numbers of locally sparse graphs and a Ramsey type problem
• New lower bounds for the independence number of sparse graphs and hypergraphs
• Coloring graphs with locally few colors
• On the independence number of sparse graphs

Cites work

• A note on odd cycle-complete graph Ramsey numbers
• A note on Ramsey numbers
• A note on the independence number of triangle-free graphs
• Asymptotic upper bounds for Ramsey functions
• Coloring graphs with sparse neighborhoods
• Cycles of even length in graphs
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• Independence numbers of locally sparse graphs and a Ramsey type problem
• On a problem of K. Zarankiewicz
• On book-complete graph Ramsey numbers
• On cycle—Complete graph ramsey numbers
• Ramsey numbers of some bipartite graphs versus complete graphs
• The independence number of dense graphs with large odd girth
• The independence number of graphs with a forbidden cycle and Ramsey numbers

Cited in

(4)

• Sparse hypergraphs with low independence number
• Randomly finding independent sets in locally sparse graphs
• Independent transversals in locally sparse graphs
• On the Lovász Theta Function for Independent Sets in Sparse Graphs

This page was built for publication: Lower bounds for independence numbers of some locally sparse graphs

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