On the independence number of random graphs
From MaRDI portal
Publication:923109
DOI10.1016/0012-365X(90)90149-CzbMath0712.05052DBLPjournals/dm/Frieze90OpenAlexW2079330337WikidataQ57401600 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 (53)
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
This page was built for publication: On the independence number of random graphs
