A note on the sharp concentration of the chromatic number of random graphs

No abstract is available for this paper.

• Publication year

  1991

• Venue

  Comb.

• Publication date

  1991-09-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/BF01205080
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Sharp concentration of the chromatic number on random graphsGn, p

  1987cited by this paper
• Graph Theory: An Introductory Course

  1980cited by this paper

• Balanced colorings of Erd\H{o}s-R\'enyi hypergraphs

  2025influential citation
• Two-Point Concentration of the Domination Number of Random Graphs

  2024cites this paper
• On the Concentration of Values of j-Chromatic Numbers of Random Hypergraphs

  2023cites this paper
• On the Chromatic Number of Random Regular Hypergraphs

  2022cites this paper
• The oriented chromatic number of random graphs of bounded degree

  2022influential citation
• Two-Point Concentration of the Independence Number of the Random Graph

  2022cites this paper
• On the chromatic number of graphons

  2021cites this paper
• On the Chromatic Number in the Stochastic Block Model

  2021cites this paper
• How does the chromatic number of a random graph vary?

  2021cites this paper
• On the strong chromatic number of a random 3-uniform hypergraph

  2021cites this paper
• Bounds for List-Decoding and List-Recovery of Random Linear Codes

  2020cites this paper
• On the Chromatic Numbers of Random Hypergraphs

  2020cites this paper
• Estimating the r-colorability threshold for a random hypergraph

  2020cites this paper
• The Chromatic Number of Dense Random Block Graphs

  2020cites this paper
• Vector Colorings of Random, Ramanujan, and Large-Girth Irregular Graphs

  2019cites this paper
• Two values of the chromatic number of a sparse random graph

  2019influential citation
• Non-concentration of the chromatic number of a random graph

  2019cites this paper
• Complexity of Coloring Random Graphs

  2018cites this paper
• 1 3 A pr 2 01 8 Hypergraph coloring up to condensation

  2018cites this paper
• Scan Statistics on Graphs and Networks

  2018cites this paper
• The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime

  2017cites this paper
• Waiter–Client and Client–Waiter games

  2017cites this paper
• On the concentration of the chromatic number of a random hypergraph

  2017cites this paper
• On the Number of Solutions in Random Graph k-Colouring

  2016cites this paper
• The Chromatic Number of Random Graphs for Most Average Degrees

  2016cites this paper
• Independent sets in graphs

  2016cites this paper
• On MAXCUT in strictly supercritical random graphs, and coloring of random graphs and random tournaments

  2016cites this paper
• Colourings of random graphs

  2016cites this paper
• Независимые множества в графах

  2016cites this paper
• The chromatic number of dense random graphs

  2016cites this paper
• Topics in Chromatic Graph Theory: Colouring random graphs

  2015influential citation
• Hypergraph coloring up to condensation

  2015cites this paper
• 9-30-2014 Between 2-and 3-colorability

  2015cites this paper
• Local Convergence of Random Graph Colorings

  2015cites this paper
• Order-Optimal Rate of Caching and Coded Multicasting With Random Demands

  2015cites this paper
• Topics in Ramsey Theory

  2014cites this paper
• Between 2- and 3-Colorability

  2014cites this paper
• Planting Colourings Silently

  2014cites this paper
• Induced Acyclic Tournaments in Random Digraphs: Sharp Concentration, Thresholds and Algorithms

  2014cites this paper
• Complexity of coloring random graphs : zooming in on the hardest part ∗

  2014cites this paper
• Random Structures and Algorithms

  2014cites this paper
• The Origins of the Theory of Random Graphs

  2013cites this paper
• Containing Viral Spread on Sparse Random Graphs: Bounds, Algorithms, and Experiments

  2013cites this paper
• Average-case complexity of backtrack search for coloring sparse random graphs

  2013cites this paper
• Probabilistic Combinatorics

  2013cites this paper
• On the chromatic number of random regular graphs

  2013cites this paper
• The Phase Transition in the Erdős-Rényi Random Graph Process

  2013cites this paper
• Chasing the K-Colorability Threshold

  2013cites this paper
• On the Concentration of the Domination Number of the Random Graph

  2012cites this paper
• Coloring random graphs online without creating monochromatic subgraphs

  2011cites this paper
• Asymptotic behaviour of the complexity of coloring sparse random graphs∗

  2011cites this paper
• Determining the expected runtime of an exact graph coloring algorithm

  2011influential citation
• Maximum Clique, Maximum Independent Set, and Graph Coloring Problems

  2011cites this paper
• Determining the expected runtime of exact graph coloring

  2010cites this paper
• Degree Sequences of Random Bipartite Graphs

  2010cites this paper
• Colouring empires in random trees

  2010cites this paper
• Clique , independent set , and graph coloring

  2010cites this paper
• Martingales on Trees and the Empire Chromatic Number of Random Trees

  2009cites this paper
• On the concentration of the chromatic number of random graphs

  2008cites this paper
• Two-point concentration in random geometric graphs

  2008cites this paper
• Two new Probability inequalities and Concentration Results

  2008cites this paper
• Two remarks on the Burr-Erdos conjecture

  2008cites this paper
• A New Probability Inequality Using Typical Moments and Concentration Results

  2008cites this paper
• Notes on Extremal Graph Theory

  2008cites this paper
• On the chromatic number of random d-regular graphs

  2008influential citation
• On the chromatic number of random graphs

  2007cites this paper
• The chance that a convex body is lattice-point free: A relative of Buffon's needle problem

  2007cites this paper
• On the Strong Chromatic Number of Random Graphs

  2007cites this paper
• Concentration Properties of Extremal Parameters in Random Discrete Structures

  2006cites this paper
• The Threshold for the Balancedness of Colored Graphs

  2006cites this paper
• Random regular graphs of non-constant degree: Concentration of the chromatic number

  2005influential citation
• Random regular graphs of non-constant degree: distribution of edges and applications

  2005influential citation
• On the distribution of edges in random regular graphs

  2005influential citation
• Optimization and information retrieval techniques for complex networks

  2005cites this paper
• Spectral Techniques, Semidefinite Programs, and Random Graphs

  2005influential citation
• The Chromatic Number of Random Regular Graphs

  2004influential citation
• The two possible values of the chromatic number of a random graph

  2004cites this paper
• How Sharp is the Concentration of the Chromatic Number?

  2004cites this paper
• The Lovász Number of Random Graphs

  2003influential citation
• Maximum independent set and related problems, with applications

  2003cites this paper
• Coloring Random Graphs — an Algorithmic Perspective

  2002cites this paper
• Randomness and Pseudo-Randomness in Discrete Mathematics

  2002cites this paper
• Sparse Graphs Usually Have Exponentially Many Optimal Colorings

  2002cites this paper
• Derandomization in Combinatorial Optimization

  2001cites this paper
• The Probablistic Method

  2000cites this paper
• On the Choice Number of Random Hypergraphs

  2000cites this paper
• A Sharp Threshold for k-Colorability

  1999cites this paper
• List Coloring of Random and Pseudo-Random Graphs

  1999influential citation
• Threshold phenomena in random graph colouring and satisfiability

  1999cites this paper
• The Graph Coloring Problem: A Bibliographic Survey

  1998cites this paper
• On-Line Coloring of Sparse Random Graphs and Random Trees

  1997cites this paper
• The concentration of the chromatic number of random graphs

  1997influential citation
• Random I-Cororable Graphs

  1995cites this paper
• On the minimal number of edges in

  year unknowncites this paper