Independence numbers of locally sparse graphs and a Ramsey type problem

DOI<271::AID-RSA1>3.0.CO;2-U 10.1002/(SICI)1098-2418(199610)9:3<271::AID-RSA1>3.0.CO;2-UzbMath0876.05049OpenAlexW2078604563MaRDI QIDQ4716329

Noga Alon

Publication date: 26 November 1996

Full work available at URL: https://doi.org/10.1002/(sici)1098-2418(199610)9:3<271::aid-rsa1>3.0.co;2-u

zbMATH Keywords

independence numbersparse graphsRamsey type theorem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Generalized Ramsey theory (05C55)

Related Items

The list chromatic number of graphs with small clique number, The independence numbers of weighted graphs with forbidden cycles, Combinatorial optimization. Abstracts from the workshop held November 9--15, 2014., Bounding \(\chi\) by a fraction of \(\Delta\) for graphs without large cliques, On the Lovász Theta Function for Independent Sets in Sparse Graphs, On the average size of independent sets in triangle-free graphs, Graph and hypergraph colouring via nibble methods: a survey, Independence and matching number of some graphs, Local and global colorability of graphs, New bounds on the Ramsey number \(r ( I_m , L_n )\), Linear Turán Numbers of Linear Cycles and Cycle-Complete Ramsey Numbers, Lower bounds for independence numbers of some locally sparse graphs, On locally Gabriel geometric graphs, Independent sets in graphs, On independent sets in hypergraphs, On Constant Time Approximation of Parameters of Bounded Degree Graphs, On the density of subgraphs in a graph with bounded independence number, New lower bounds for permutation arrays using contraction, Randomly finding independent sets in locally sparse graphs