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.