z-logo
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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom