On the chromatic forcing number of a random graph

AbstractWhen we wish to compute lower bounds for the chromatic number χ(G) of a graph G, it is of interest to know something about the ‘chromatic forcing number’ fχ(G), which is defined to be the least number of vertices in a subgraph H of G such that χ(H) = χ(G). We show here that for random graphs Gn,p with n vertices, fχ(Gn,p) is almost surely at least (12−ε)n, despite say the fact that the largest complete subgraph of Gn,p has only about log n vertices