On the chromatic number of random graphs

No abstract is available for this paper.

• Publication year

  2007

• Venue

  J. Comb. Theory B

• Publication date

  2007-07-09

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.jctb.2007.11.009
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Probabilistic Method

  2015cited by this paper
• Random graphs

  2006cited by this paper
• A comparison of graph coloring heuristics for register allocation based on coalescing in interval graphs

  2004cited by this paper
• How Much Backtracking Does It Take to Color Random Graphs? Rigorous Results on Heavy Tails

  2004cited by this paper
• The two possible values of the chromatic number of a random graph

  2004influential reference
• The Probabilistic Method: Alon/Probabilistic Method

  2004cited by this paper
• Polynomial iterative algorithms for coloring and analyzing random graphs.

  2003cited by this paper
• Coloring Random Graphs — an Algorithmic Perspective

  2002cited by this paper
• Almost all graphs with average degree 4 are 3-colorable

  2002cited by this paper
• Coloring random graphs

  2002cited by this paper
• RANDOM GRAPHS (Wiley Interscience Series in Discrete Mathematics and Optimization)

  2001cited by this paper
• Random graphs

  2000cited by this paper
• A Sharp Threshold for k-Colorability

  1999cited by this paper
• The concentration of the chromatic number of random graphs

  1997influential reference
• Zero knowledge and the chromatic number

  1996cited by this paper
• A note on the sharp concentration of the chromatic number of random graphs

  1991cited by this paper
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning

  1991cited by this paper
• The chromatic number of random graphs

  1988cited by this paper
• Sharp concentration of the chromatic number on random graphsGn, p

  1987cited by this paper

• The fractional chromatic number of random graphs

  2026cites this paper
• Concentration of rainbow k-connectivity of a multiplex random graph

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

  2023cites this paper
• Estimating the strong r-colorability threshold in random hypergraphs

  2023cites this paper
• Large Independent Sets in Recursive Markov Random Graphs

  2022cites this paper
• On Two Limit Values of the Chromatic Number of a Random Hypergraph

  2022cites this paper
• Two-Point Concentration of the Independence Number of the Random Graph

  2022cites this paper
• О двух предельных значениях хроматического числа случайного гиперграфа

  2022cites 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
• On the Chromatic Number in the Stochastic Block Model

  2021cites this paper
• On the Chromatic Number of a Random 3-Uniform Hypergraph

  2021cites this paper
• Combinatorics

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

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

  2020cites this paper
• Non-concentration of the chromatic number of a random graph

  2019cites this paper
• Clique coloring of binomial random graphs

  2018cites this paper
• Lower bounds on the chromatic number of random graphs

  2018cites this paper
• The Multilevel Splitting algorithm for graph colouring with application to the Potts model

  2017cites this paper
• Graph Orientations and Linear Extensions

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

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

  2012cites this paper
• A note on the chromatic number of a dense random graph

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

  2008cites this paper
• On The Span Of A Random Channel Assignment Problem

  2007influential citation