Phase Transition of Degeneracy in Minor-Closed Families

DOI10.1016/J.AAM.2023.102489arXiv1912.02375MaRDI QIDQ6330485FDOQ6330485

Authors: Chun-Hung Liu, Fan Wei 

Publication date: 4 December 2019

Abstract: Given an infinite family $mathcalG$ of graphs and a monotone property $mathcalP$, an (upper) threshold for $mathcalG$ and $mathcalP$ is a "fastest growing" function $p:mathbbNo[0,1]$ such that $li{m}_{noinfty}Pr(G_n(p(n))inmathcalP)=1$ for any sequence $(G_n{)}_{ninmathbbN}$ over $mathcalG$ with $li{m}_{noinfty}lvertV(G_n)vert=infty$, 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 for the graph property of being $(r-1)$-degenerate, which is one fundamental graph property with many applications. Even a constant factor approximation for the upper threshold for all pairs $(r,H)$ is expected to be very difficult 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 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)$. The results generalize to arbitrary proper minor-closed families and the properties of being $r$-colorable, being $r$-choosable, or containing an $r$-regular subgraph, respectively.

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42) Structural characterization of families of graphs (05C75) Graph minors (05C83)

This page was built for publication: Phase Transition of Degeneracy in Minor-Closed Families

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6330485)