For k = 4,5 this is shown by exhibiting special k-critical graphs on 20, respectively 17, vertices, each of which allows no construction of the desired type. For k ≥ 6 and k ≠ 8 it is shown that there exists a general construction of such k-critical graphs. The complete answer is obtained by quoting the example of Catlin [1979] for the remaining case of k = 8.
The similar question for the restriction of Hajós's construction formulated by Ore [1967] also has a negative answer for k ≥ 4. This is shown by joining complete graphs completely to the special 4-critical graph mentioned above.
It remains open, whether one may restrict the construction in such a way that operation (a) is used only on pairs of k-critical graphs, and yet be able to construct all k-critical graphs.
Tommy R. Jensen, October 1, 1997.