On \(F(j)\)-graphs and their applications (Q2747179)

The author generalizes a result of Erdős and Gallai that every \(r\)-regular graph of order \(n\), with \(r<n-1\), has chromatic number at most \(3n/5\). The covering number of a graph is the chromatic number of its complement. An \(F(j)\)-graph is a \((j-1)\)-regular graph of minimum order \(f(j)\) whose covering number exceeds \(f(j)/2\). It is shown that any \(F(j)\)-graph has odd order, is 2-connected and Hamiltonian. An upper bound for \(f(j)\) is obtained by the actual construction of a \((j-1)\)-regular triangle-free Hamiltonian graph. This leads to a proof of the following theorem: For any odd integer \(j\geq 3\), one has \(f(j)=\frac{5}{2}(j-1)\) if \(j\equiv 3\pmod 4\) and \(f(j)=1+\frac{5}{2}(j-1)\) if \(j\equiv 1\pmod 4\). An easy consequence of this is the following generalization of an Erdős-Gallai result: Any \(r\)-regular graph of order \(n\) with odd \(j:=n-r \geq 3\) has chromatic number at most \(\frac{f(j)+1}{2f(j)}n\), and this bound is achieved precisely by those graphs with complement equal to a disjoint union of \(F(j)\)-graphs.