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

Abstract

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\ge 3$ and show that $f(j)=5(j–1)/2\$if\text{(}j\equiv 3(\mathrm{mod}4)$, and $f(j)=1+5(j–1)/2$ if $j\equiv 1(\mathrm{mod}4)$.