2
$\begingroup$

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$

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.