Problem 11.7: Hajós Constructions of Critical Graphs

Problem 11.7 has been solved: The answer is negative, as shown in the paper [T.R. Jensen and G.F. Royle, Hajós constructions of critical graphs, to appear in J. Graph Theory].

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.

Back to Overview menu
Back to Graph Coloring Problems homepage

Last modified July 21, 1998 Tommy R. Jensen