Random instances of a graph coloring problem are hard

Abstract

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.