Chromatic Thresholds in Dense Random Graphs

Author(s)

Allen, Peter ; Bottcher, Julia ; Griffiths, Simon ; Kohayakawa, Yoshiharu ; Morris, Robert

• Document type: Journal article
• Source: RANDOM STRUCTURES & ALGORITHMS; v. 51, n. 2, p. 185-214, SEP 2017.
• Web of Science Citations: 0

Abstract

The chromatic threshold delta(chi) (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 subset of G(n, p) with minimum degree delta(G) >= dpn has bounded chromatic number. The study of the parameter delta(chi) (H) := delta(chi) (H, 1) was initiated in 1973 by Erdos and Simonovits, and was recently determined for all graphs H. In this paper we show that delta(chi) (H, p) = delta(chi) (H) for all fixed p epsilon (0, 1), but that typically delta(chi) (H, p) not equal delta(chi) (H) if p = 0(1). We also make significant progress towards determining delta(chi) (H, p) for all graphs H in the range p = n(-0(1)). In sparser random graphs the problem is somewhat more complicated, and is studied in a separate paper. (C) 2017 Wiley Periodicals, Inc. (AU)

• FAPESP's process: 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science
• Grantee: Carlos Eduardo Ferreira
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 09/17831-7 - Embedding and packing problems in extremal graph theory
• Grantee: Julia Boettcher
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• FAPESP's process: 10/09555-7 - Embedding, randomised and structural problems in extremal graph theory
• Grantee: Peter David Allen
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• FAPESP's process: 13/07699-0 - Research, Innovation and Dissemination Center for Neuromathematics - NeuroMat
• Grantee: Oswaldo Baffa Filho
• Support Opportunities: Research Grants - Research, Innovation and Dissemination Centers - RIDC