# Chromatic Polynomials of Circulant Graph With Two Parameters

I have been working with the chromatic polynomials of circulant graphs of prime order $$p$$ with two distinct parameters, i.e.

$$P_{p,i,j}(x):= P(C_{p}(i,j),x)$$ with $$1 \leq i \neq j \leq \ n/2.$$

In this regard, I have a couple of questions. Let $$p$$ be a prime number as above, and $$1 \leq i' \neq j' \leq \ n/2$$ and $$1 \leq i \neq j \leq \ n/2$$. Are the following conjectural identities true?

1. $$P_{p,i,j}(x) \stackrel{?}{=} P_{p,i',j'}(x)$$; (No. Counter example by Jeremy Martin: $$C_{11}(1,2)$$ and $$C_{11}(1,3)$$)
2. $$P_{p,i,j}(p) \stackrel{?}{\leq} e^2 * p^p$$.

These questions seem to answer in positive in experiments, but I have not found literature that helps me to prove (or disprove) these statements. Any literature suggestions or ideas on how to approach them would be very helpful.

Best regards

• Dear Abraham, is there any question you want to formulate in regards to your findings? I'd say a number of clearly stated questions would help enormously. – SashaKolpakov Dec 19 '18 at 22:37
• Yes indeed Sasha; It would be very helpful if someone can direct me to some literature or if someone would like to discuss some ideas on how to prove (or disprove) the experiment-based observations I did. – Abraham G Dec 20 '18 at 8:18

I assume that $$C_p(i,j)$$ means the graph with vertices $$0,\dots,p-1$$ and edges between each pair of vertices with difference $$i$$ or $$j$$ mod $$p$$. If that is the case, then identity 1 does not appear to be true in general; Sage gives different chromatic polynomials for $$C_{11}(1,2)$$ and $$C_{11}(1,3)$$. (By the way, you may as well assume $$i=1$$, because $$C_p(i,j)\cong C_p(1,j/i)$$, with the quotient taken in $$\mathbb{Z}/p\mathbb{Z}$$.)