The graph constructions ofHaj�s and Ore
Alasdair Urquhart · Journal of Graph Theory · 1997
A well-known theorem of Hajós shows that any graph with chromatic number at least q contains a subgraph constructible from the complete graph Kq by repeated application of two simple operations. Ore proved that the theorem still holds if the two operations are replaced by a single operation combining both of Hajós's operations. This note answers a question of Jensen and Toft by showing that for each q the classes of graphs constructible by these two methods are the same. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 211–215, 1997