{"id":"arxiv/2609.03184","url":"https://arxiv.org/abs/2609.03184","tags":["math.CO"],"score":0,"title":"On uniquely colorable Cayley graphs","domain":"math.CO","source":"arxiv","authors":["Milan Bašić"],"reviews":0,"subject":"math.CO","summary":"We resolve two open problems regarding uniquely colorable Cayley graphs posed by Klotz and Sander (2017). First, we construct an infinite family of uniquely 3-colorable integral circulant graphs with a clique number of 2. This provides a negative answer to Problem 3.6, which asks whether every uniquely colorable circulant graph satisfies $χ(G) = ω(G)$. Because verifying unique colorability inherently relies on the exact independence number, we demonstrate that traditional spectral bounds fail to tightly capture this parameter, necessitating a rigorous combinatorial proof based on exact…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-02","reactions":{}}