# Maximum Chromatic number of Cayley Graphs with large degree

It is known that there does not exist a regular graph of order $$n$$ with clique size greater than $$\lceil\frac{n}{2}\rceil$$. My question pertains to Cayley graphs with large degree, say $$\ge \frac{n}{2}$$ and not complete. I think the maximum chromatic number is $$\lceil\frac{3n}{5}\rceil$$. As an example of a graph attaining the attaining the upper bound, we consider the complete graph with order divisible by $$5$$ and remove a $$2$$- factor. The two factor we remove is the disjoint union of $$\frac{n}{5}$$ $$5$$-cycles. Then, the chromatic number is $$\frac{3n}{5}$$.

Are there any Cayley graphs with degree $$\ge\frac{n}{2}$$, and not complete, such that their chromatic number exceeds $$\lceil\frac{3n}{5}\rceil$$. And, also, are there other Cayley graphs with chromatic numbers between $$\lceil\frac{n}{2}\rceil$$ and $$\lceil\frac{3n}{5}\rceil$$

## 1 Answer

Erdős and Gallai showed in their paper Solution of a problem of Dirac then the chromatic number of a non-complete regular graph is at most $$\frac{3}{5}n$$.

Caccetta and Pullman constructed in their paper Regular graphs with prescribed chromatic number connected $$k$$-chromatic regular graphs on $$n$$ vertices for all $$k > 1$$ and $$n \geq \frac{5}{3}k$$. You can check their construction to see whether it can be adapted to give Cayley graphs.