Premium
Chromatic thresholds in dense random graphs
Author(s) -
Allen Peter,
Böttcher Julia,
Griffiths Simon,
Kohayakawa Yoshiharu,
Morris Robert
Publication year - 2017
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20708
Subject(s) - infimum and supremum , random graph , chromatic scale , combinatorics , mathematics , brooks' theorem , discrete mathematics , graph , random regular graph , bounded function , indifference graph , 1 planar graph , chordal graph , mathematical analysis
The chromatic thresholdδ χ ( H , p ) of a graph H with respect to the random graph G ( n, p ) is the infimum over d > 0 such that the following holds with high probability: the family of H ‐free graphs G ⊂ G ( n , p ) with minimum degree δ ( G ) ⩾ d p n has bounded chromatic number. The study of the parameterδ χ ( H ) : = δ χ ( H , 1 ) was initiated in 1973 by Erdős and Simonovits, and was recently determined for all graphs H . In this paper we show thatδ χ ( H , p ) = δ χ ( H ) for all fixed p ∈ ( 0 , 1 ) , but that typicallyδ χ ( H , p ) ≠ δ χ ( H ) if p = o ( 1 ) . We also make significant progress towards determiningδ χ ( H , p ) for all graphs H in the range p = n − o ( 1 ). In sparser random graphs the problem is somewhat more complicated, and is studied in a separate paper. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 185–214, 2017