On the independence number of random graphs
From MaRDI portal
Publication:923109
DOI10.1016/0012-365X(90)90149-CzbMath0712.05052OpenAlexW2079330337WikidataQ57401600 ScholiaQ57401600MaRDI QIDQ923109
Publication date: 1990
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0012-365x(90)90149-c
Related Items
The symmetry in the martingale inequality, Percolation with small clusters on random graphs, On independent sets in random graphs, Constructions of independent sets in random intersection graphs, Colouring Non-sparse Random Intersection Graphs, Random Instances of Problems in NP – Algorithms and Statistical Physics, On Some Combinatorial Properties of Random Intersection Graphs, Multicolor Ramsey Numbers For Complete Bipartite Versus Complete Graphs, Independence and matching numbers of unicyclic graphs from null space, Counterexamples to a Conjecture of Harris on Hall Ratio, On the independence number of Cayley digraphs of rectangular groups, Distributed algorithms for random graphs, On vertex independence number of uniform hypergraphs, The largest hole in sparse random graphs, On the chromatic number in the stochastic block model, Extremal bipartite independence number and balanced coloring, Independence numbers of random sparse hypergraphs, Two-Point Concentration of the Independence Number of the Random Graph, Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback, Small maximal matchings in random graphs., Which subsets of an infinite random graph look random?, Algorithmic obstructions in the random number partitioning problem, Null decomposition of unicyclic graphs, Dismantling Sparse Random Graphs, On the concentration of the independence numbers of random hypergraphs, Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics, Two faces of greedy leaf removal procedure on graphs, Random bipartite posets and extremal problems, Disproving the normal graph conjecture, Subgroup growth of right‐angled Artin and Coxeter groups, Two Hardness Results on Feedback Vertex Sets, On the independence and chromatic numbers of random regular graphs, Generalized random sequential adsorption on Erdős-Rényi random graphs, Random regular graphs of high degree, A sharp concentration inequality with applications, On the chromatic number of non-sparse random intersection graphs, An almost quadratic bound on vertex Folkman numbers, The chromatic number of random graphs, Unnamed Item, Existential monadic second order convergence law fails on sparse random graphs, Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs, Induced acyclic tournaments in random digraphs: sharp concentration, thresholds and algorithms, Independent Sets in Random Graphs from the Weighted Second Moment Method, Improved Bounds on Induced Acyclic Subgraphs in Random Digraphs, Large independent sets in random regular graphs, More spectral bounds on the clique and independence numbers, Cliques and chromatic number in multiregime random graphs, On the Concentration of the Domination Number of the Random Graph, On the Chromatic Index of Random Uniform Hypergraphs, Large Induced Matchings in Random Graphs, Graph imperfection. II, The maximum clique problem, Optimal low-degree hardness of maximum independent set
Cites Work
- Unnamed Item
- Unnamed Item
- Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
- Expose-and-merge exploration and the chromatic number of a random graph
- On colouring random graphs
- Cliques in random graphs
- Some Results on the Complete and Almost Sure Convergence of Linear Combinations of Independent Random Variables and Martingale Differences
