The graph colorability (COL), as well as the propositional satisfiability (SAT), is a popular decision problem containing combinatorial search, which has been studied from the viewpoints of computational complexity and search algorithms. Those problems both are also interesting as the theme of heuristics. There are many research reports as of the computational comlexity of COL. For example, 3-paths of Vlasie, minimal unsolvable subproblems (MUSs) of Mammen et al., and frozen developments of Culberson et al. are possible candidates of order parameter to explain the mechamism which may make COLs exceptionally hard. We propose in this paper an ordered method to produce 3-colorability problems (3COLs) which are exceptionally hard for not only usual backtracking algorithms adopting Brelaz heuristics, but also smallk coloring program. The instances generated by our procedure have the following properties: (1)the instances themselves are large 4-critical graphs, (2)they have no near 4-cliques (n4c's; 4-cliques with one edge removed), and (3)they keep the degree of every nodes to 3 or 4, nearly regular.
