Erdos and Gallai (1963) showed that every r-regular graph of sufficiently large order n has chromatic number at most 3n/5, and this
bound is achieved precisely for those graphs with complement equal to a disjoint union of 5-cycles.

We generalize this result by considering the problem of determining a (j-1)-regular graph G of minimum order f(j) such that the chromatic number of the complement of G exceeds f(r)/2.
Such a graph will be called an F(j)-graph.
We produce an F(j)-graph for all positive odd integers j, showing that f(j)=5(j-1)/2 when j is congruent to 3 mod 4 and f(j)=1+5(j-1)/2 when j is congruent to 1 mod 4.