Original title: On uniquely colorable Cayley graphs
Milan Bašić · September 2026
Mathematicians studied networks called Cayley graphsGraphs constructed from a group, where vertices are group elements and edges represent multiplication by specific elements., which are built using algebraic groups. They wanted to know if certain networks can be colored in only one valid way, meaning connected points never share a color. Past researchers asked two open questions about this. To answer the first, the authors built a whole family of circulant graphs that need 3 colors, where the largest fully connected group of points has size 2. Because standard formulas using matrix math failed to count the exact independent points, they verified the coloring through direct structural proofs. For the second question, they built uniquely colorableA graph that can be colored with the minimum number of colors in only one way. networks over nonabelian groups by using special subgroup partitions. These discoveries solved both open problems.
Imagine you have a set of jobs to assign to workers, where each job can only be done by certain workers. Normally, there might be multiple ways to assign jobs using the minimum number of workers. But sometimes, there's exactly one way to assign jobs with three workers, even though no three workers can all work together directly. In this paper, the jobs and workers form a graph, and the unique assignment corresponds to the unique coloring. The researchers found such setups by using group theory to structure the connections.
This advances graph theory by answering long-standing questions, showing that common assumptions about coloring aren't always true. It gives mathematicians new tools to study how colors and structures relate in networks.
The abstract does not discuss computational efficiency or real-world applications. It focuses on theoretical constructions for specific graph types and does not explore broader generalizations or algorithmic aspects.
Ask anything about this paper. Answers come from its abstract, and say so when the abstract doesn't cover your question.
On uniquely colorable Cayley graphs — Milan Bašić
Abstract licence: CC0
Explanation generated by Synthesis from the abstract — it is not the original paper. This is a preprint, so it hasn't necessarily been peer reviewed.