Polynomial method for perfect 2-colourings of circulant graphs

2021/11/21 by Svyatoslav Novikov, Novikov, Svyatoslav
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2111.10796

openalex publication_date 2021/11/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 ≤ 2k + (b+c)/(q^t) for all positive integers t and primes q satisfying (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.

Related

• Block Circulant Graphs and the Graphs of Critical Pairs of a Crown
• Chromatic polynomials of 2-edge coloured graphs
• On factorisations of complete graphs into circulant graphs and the Oberwolfach Problem
• A Contribution to the Theory of Chromatic Polynomials
• Prime and polynomial distances in colourings of the plane