Critical Subgraphs of a Random Graph

  • Michael Molloy
  • Bruce Reed
DOI: https://doi.org/10.37236/1467

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.

Published
1999-09-06
How to Cite
Molloy, M., & Reed, B. (1999). Critical Subgraphs of a Random Graph. The Electronic Journal of Combinatorics, 6(1), R35. https://doi.org/10.37236/1467
Issue
Volume 6 (1999)
Article Number
R35