As a corollary it follows that the question whether or not a given graph is Hajós-k-constructible is always decidable: It suffices to calculate its chromatic number.
Urquhart remarked to us that the proof is not hard, and we have indeed been able to construct an argument of our own which shows the statement. A written proof will be made available at a later time.
For k = 2 it can be proved along similar lines that the class of graphs of chromatic number at least 2 (i.e. graphs with at least one edge) and with at least three vertices coincides with the class of graphs obtained by repeated applications of the Ore-construction starting from copies of P2, the path with two edges. The answer to Problem 11.5 for k = 2 is obviously positive.
We learned of this solution after contacting the authors of the very interesting paper [T. Pitassi and A. Urquhart, The complexity of the Hajós calculus, SIAM J. Discrete Math. 8 (1995) 464-483], which describes relations between the Hajós construction and a family of proof systems in logic known as Extended Frege Systems.
Among other results, the paper proves that for a restricted version of the Hajós construction, which for k > 2 remains powerful enough to construct all graphs of chromatic number at least k, there exist infinitely many constructible graphs G for k = 4 for which the smallest number of steps needed in the construction of G grows as an exponential function of the size of G.
See also Problem 11.6 for a discussion of the length of Hajós-proofs.
January 1996, T.R. Jensen and B. Toft.