An exact threshold theorem for random graphs and the node-packing problem

The usual linear relaxation of the node-packing problem contains no useful information when the underlying graph G has the property of “bicriticality.” We consider a sparse random graph G_n(m) obtained in the usual way from a random directed graph with fixed out-degree m and show that the probability that G_n(2) is bicritical tends to $\text{(1−2e}{}^{\mathrm{-2}}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$ as n→∞. This confirms a conjecture by G. R. Grimmett and W. R. Pulleyblank (Oper. Res. Lett., in press).