replica symmetry breaking in minimal vertex covers, Ref. [@baugolloctrans] for a localization problem, and, in a numerical context, Ref. [@baugolmom] where an anomaly close to the eigenvalue $0$ in the spectrum of random adjacency matrices was observed).

The paper is organized as follows. The general definitions have been regrouped in section \[sec:defs\]. They are standard and should be used only for reference.

In section \[sec:core\] we define leaf removal, leaf removal processes obtained by iteration of leaf removals and the “core” for an arbitrary graph.

Section \[sec:coreperco\] presents our derivation of the main results for large random graphs. The analytical formulæ for $i(\alpha)$, $c(\alpha)$ and $l(\alpha)$ are given.

In section \[sec:numsim\], these formulæ are checked against Monte-Carlo simulations of leaf removal processes, which we also use for the finite size scaling analysis in the critical region. This leads us to the definition and numerical evaluation of many new critical exponents. In particular, we give good evidence that the core percolation exponents (at $\alpha =e$) are not the same as the critical exponents of standard percolation (at $\alpha =1$). Even if core percolation on a random graph can presumably be seen as a mean field approximation for core percolation on (finite 