Hajós constructions of critical graphs
Tommy R. Jensen, Gordon Royle · UWA Profiles and Research Repository (University of Western Australia) · 1999
For every k greater than or equal to 4 there exists a k-critical graph that is not Hajos-k-constructible through a sequence of k-critical graphs. This completely answers a question of G. Hajos, which has been answered previously only for k = 8 with an example given by P. Catlin. Also the corresponding problem for Ore's construction has the analogous answer for all k greater than or equal to 4. (C) 1999 John Wiley & Sons, Inc.