On \(F(j)\)-Graphs and Their Applications

Erdős and Gallai (1963) showed that any \(r\)-regular graph of order \(n\), with \(r < n-1\), has chromatic number at most \({3n}/{5}\), and this bound is achieved by precisely those graphs with complement equal to a disjoint union of 5-cycles.

We are able to 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(j)}/{2}\). Such a graph will be called an \(F(j)\)-\emph{graph}. We produce an \(F(j)\)-graph for all odd integers \(j \geq 3\) and show that \(f(j) = {5(j – 1)}/{2}$ if \(j \equiv 3 \pmod{4}\), and \(f(j) = 1 + {5(j – 1)}/{2}\) if \(j \equiv 1 \pmod{4}\).