They also pointed out that certain classes of graphs can be shown to be constructible in a polynomial number of steps.
These results may be seen as a significant partial answers to Problem 11.6.
In the same paper it is remarked that Jason Brown has proved (unpublished) that disallowing operation (c) except in the very last step of the construction of G does not essentially alter the complexity compared to allowing operations (a), (b), and (c) in each step.
In connection with Problem 11.5 (which has been solved by A. Urquhart, see the corresponding file in this archive), we have found a proof for k > 2 that disallowing operation (c) does not essentially change the complexity of an Ore type construction of G when compared to allowing operation (c) only at the very last step.
T.R. Jensen and B. Toft, January 1996.