Phase transition of degeneracy in minor-closed families

Chun Hung Liu, Fan Wei

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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 limn→∞⁡Pr⁡(Gn(p(n))∈P)=1 for any sequence (Gn)n∈N over G with limn→∞⁡|V(Gn)|=∞, where Gn(p(n)) is the random subgraph of Gn 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 languageEnglish (US)
Article number102489
JournalAdvances in Applied Mathematics
StatePublished - May 2023

All Science Journal Classification (ASJC) codes

  • Applied Mathematics


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


Dive into the research topics of 'Phase transition of degeneracy in minor-closed families'. Together they form a unique fingerprint.

Cite this