2 papers
math.CO2025
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 (-labellings studied in the conte…
math.RA2025
Network Satisfaction over Four-Atom Relation Algebras: Complexity and Representations
Manuel Bodirsky, Moritz Jahn, Simon Knäuer +2
Andréka and Maddux classified the relation algebras with at most 3 atoms, and in particular they showed that all of them are representable. Cristani and Hirsch showed that the netw…