Polynomial method for perfect 2-colourings of circulant graphs

Abstract

In this paper we prove that if an infinite circulant graph with $k$ distances has a perfect $2$-colouring with parameters $(b,c)$, then $b+c\le 2k+\frac{b+c}{q^t}$ for all positive integers $t$ and primes $q$ satisfying $\frac{b+c}{gcd(b,c)}⋮q^t$. In addition, we show that if $b+c=q^t$, then this necessary condition becomes sufficient for the existence of perfect $2$-colourings in circulant graphs.

14 pages

References in corpus (1)

• On the structure of spectral and tiling subsets of cyclic groups