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$

1 Answer 1

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$

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .