Hajos constructions of critical graphs

Authors
Jensen, TR Royle, GF
Citation
Tr. Jensen et Gf. Royle, Hajos constructions of critical graphs, J GRAPH TH, 30(1), 1999, pp. 37-50
Citations number
8
Categorie Soggetti
Mathematics
Journal title
JOURNAL OF GRAPH THEORY
ISSN journal
03649024 → ACNP
Volume
30
Issue
1
Year of publication
1999
Pages
37 - 50
Database
ISI
SICI code
0364-9024(199901)30:1<37:HCOCG>2.0.ZU;2-#
Abstract
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 previou sly only for k = 8 with an example given by P. Catlin. Also the correspondi ng problem for Ore's construction has the analogous answer for all k greate r than or equal to 4. (C) 1999 John Wiley & Sons, Inc.