Dimitris Achlioptas
ABSTRACT
For every d > 0, let kd be the smallest integer k such that d < 2k log k. We prove that the chromatic number of a random graph G(n,d/n) is either kd or kd+1 almost surely. If d ∈ (2k log k - log k, 2k log k) we further prove that the chromatic number almost surely equals k+1.
- D. Achlioptas and E. Friedgut. A sharp threshold for k-colorability. Random Structures Algorithms, 14(1):63--70, 1999. Google Scholar
Digital Library
- N. Alon and M. Krivelevich. The concentration of the chromatic number of random graphs. Combinatorica, 17:303--313, 1997.Google ScholarCross Ref
- N. Alon and J. H. Spencer. The probabilistic method. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience {John Wiley & Sons}, New York, second edition, 2000. With an appendix on the life and work of Paul Erdos.Google Scholar
- B. Bollobás. The chromatic number of random graphs. Combinatorica, 8(1):49--55, 1988.Google ScholarCross Ref
- B. Bollobás. Random graphs, volume 73 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, second edition, 2001.Google Scholar
- P. Erdos and A. Rényi. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Küzl., 5:17--61, 1960.Google Scholar
- S. Janson, T. Luczak, and A. Rucinski. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000.Google ScholarCross Ref
- T. Luczak. The chromatic number of random graphs. Combinatorica, 11(1):45--54, 1991.Google ScholarCross Ref
- T. Luczak. A note on the sharp concentration of the chromatic number of random graphs. Combinatorica, 11(3):295--297, 1991.Google ScholarCross Ref
- E. Shamir and J. Spencer. Sharp concentration of the chromatic number on random graphs G n,p. Combinatorica, 7(1):121--129, 1987. Google ScholarDigital Library
- J. D. Vaaler. A geometric inequality with applications to linear forms. Pacific J. Math., 83(2):543--553, 1979.Google ScholarCross Ref
Index Terms
- The two possible values of the chromatic number of a random graph
Recommendations
Infinite families of 4-chromatic Grötzsch-Sachs graphs
Let G be a 4-regular planar graph and suppose that G has a cycle decomposition S (i.e., each edge of G is in exactly one cycle of the decomposition) with every pair of adjacent edges on a face always in different cycles of S. Such graphs, called ...
On bounding the difference between the maximum degree and the chromatic number by a constant
We provide a finite forbidden induced subgraph characterization for the graph class k, for all kN0, which is defined as follows. A graph is in k if for any induced subgraph, 1+k holds, where is the maximum degree and is the chromatic number of the ...
The chromatic discrepancy of graphs
For a proper vertex coloring c of a graph G , let c ( G ) denote the maximum, over all induced subgraphs H of G , the difference between the chromatic number ( H ) and the number of colors used by c to color H . We define the chromatic discrepancy of a ...
Comments