Random instances of a graph coloring problem are hard
Ramarathnam Venkatesan, Leonid A. Levin · 1988
NP-complete problems should be hard on some (may be extremely rare) instances. But on generic instances many such problems (especially related to random graphs) have been proven easy. We show the intractability of random instances of a graph coloring problem by modifying the NP-completeness theorem.