## Abstract

Given an infinite family G of graphs and a monotone property P, an (upper) threshold for G and P is a “fastest growing” function p:N→[0,1] such that lim_{n→∞}Pr(G_{n}(p(n))∈P)=1 for any sequence (G_{n})_{n∈N} over G with lim_{n→∞}|V(G_{n})|=∞, where G_{n}(p(n)) is the random subgraph of G_{n} such that each edge remains independently with probability p(n). In this paper we study the upper threshold for the family of H-minor free graphs and the property of being (r−1)-degenerate and apply it to study the thresholds for general minor-closed families and the properties for being r-choosable and r-colorable. Even a constant factor approximation for the upper threshold for all pairs (r,H) is expected to be challenging by its close connection to a major open question in extremal graph theory. We determine asymptotically the thresholds (up to a constant factor) for being (r−1)-degenerate (and r-choosable, respectively) for a large class of pairs (r,H), including all graphs H of minimum degree at least r and all graphs H with no vertex-cover of size at most r, and provide lower bounds for the rest of the pairs of (r,H).

Original language | English (US) |
---|---|

Article number | 102489 |

Journal | Advances in Applied Mathematics |

Volume | 146 |

DOIs | |

State | Published - May 2023 |

## All Science Journal Classification (ASJC) codes

- Applied Mathematics

## Keywords

- Degeneracy
- Graph coloring
- Graph minors
- Phase transition
- Random subgraphs