A. Gyárfás, Graphs with k odd cycle lengths, Discrete Mathematics 103 (1992) 41-48.
UNFORTUNATELY this information was not put into these archives at the time. We apologize for this!
If there are only k odd cycle lengths then the possible numbers of vertices in 4-critical subgraphs also constitute a set of size bounded by some function of k (see the comments to Problem 5.6 on page 102 of Graph Coloring Problems). Thus the following conjecture would be a strengthening of Gyárfás' Theorem (except for the exact value of the function):
Conjecture If the set of vertex numbers |V(H)| of 4-critical subgraphs H of a graph G has size k, then the chromatic number of G is bounded by some function of k.
The original problem has recently been solved independently by Ingo Schiermeyer and Peter Mihók, who also obtained the solution to the corresponding problem for even cycles:
I. Schiermeyer and P. Mihók, Chromatic number of classes of graphs with prescribed cycle lengths, Manuscript, July 1997.
Abstract: There are many open problems and conjectures of P. Erdős dealing with the relation between the chromatic number of a graph and the structure of its cycle lengths. We present a polynomial time vertex-colouring algorithm called MAXBIP which either find a proper vertex k-colouring for a given graph G or constructs a sequence of at least (k-1)/2 different odd cycle lengths and of at least (k-2)/2 different even cycle lengths. As a corollary we obtain the following solution to a problem of B. Bollobás and P. Erdős: Let Co(G) and Ce(G) denote the set of odd and even cycle lengths in a graph G, respectively. Let |Co(G)| =r and |Ce(G)|=s, then the chromatic number of G is at most min{ 2r+2 , 2s+3 }. A general point of view to some related open problems is proposed.
August 12, 1997. B. Toft.