THE GRAPH CONSTRUCTIONS OF HAJOS AND ORE

A well-known theorem of Hajos shows that any graph with chromatic numb er at least q contains a subgraph constructible from the complete grap h K-q by repealed application of two simple operations. Ore proved tha t the theorem still holds if the two operations are replaced by a sing le operation combining both of Hajos's operations. This note answers a question of Jensen and Toil by showing that for each q the classes of graphs constructible by these two methods are the same. (C) 1997 John Wiley & Sons, Inc.