2025/12/07 by Bodirsky, Manuel, Guzmán-Pro, Santiago, Jahn, Moritz +2
Computer Science · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Complexity and Algorithms in Graphs
paper · doi:10.48550/arxiv.2512.06878
In this paper, we characterize graphs with circular chromatic number less than 3 in terms of certain balancing labellings studied in the context of signed graphs. In fact, we construct a signed graph which is universal for all such labellings of graphs with circular chromatic number less than 3, and is closely related to the generic circular triangle-free graph studied by Bodirsky and Guzmán-Pro. Moreover, our universal structure gives rise to a representation of the relation algebra 5665. We then use this representation to show that the network satisfaction problem described by this relation algebra belongs to NP. This concludes the full classification of the existence of a universal square representation, as well as the complexity of the corresponding network satisfaction problem, for relation algebras with at most four atoms.