Circular Chromatic Numbers, Signability, Relation Algebras, and Network Satisfaction Problems

Manuel Bodirsky, Santiago Guzmán-Pro, Moritz Jahn +2

In this paper, we characterize finite graphs with circular chromatic number less than 3 in terms of the existence of certain signings (${\mathbb{Z}}_2$-labellings studied in the conte…