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

  • $\begingroup$ 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. $\endgroup$ – SashaKolpakov Dec 19 '18 at 22:37
  • $\begingroup$ 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. $\endgroup$ – 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}$.)

| cite | improve this answer | |

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.