Critical Subgraphs of a Random Graph

Michael Molloy, Bruce Reed

Abstract


We prove that the threshold for a random graph to have a $k$-core is equal to the threshold for having a subgraph which meets a necessary condition of Gallai for being $k$-critical.


Full Text: PDF