Critical subgraphs of a random graph
Consider \(n\) vertices and a graph process obtained by successively inserting edges at random. The threshold for a graph that is almost surely \(k\)-colorable is compared to the threshold for the appearance of a \(k\)-core.
scientific article; zbMATH DE number 1345965