Circular Chromatic Numbers, Balanceability, Relation Algebras, and Network Satisfaction Problems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912753431609344 |
|---|---|
| author | Bodirsky, Manuel Guzmán-Pro, Santiago Jahn, Moritz Konečný, Matěj Winkler, Paul |
| author_facet | Bodirsky, Manuel Guzmán-Pro, Santiago Jahn, Moritz Konečný, Matěj Winkler, Paul |
| contents | 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 $56_{65}$. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_06878 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Circular Chromatic Numbers, Balanceability, Relation Algebras, and Network Satisfaction Problems Bodirsky, Manuel Guzmán-Pro, Santiago Jahn, Moritz Konečný, Matěj Winkler, Paul Combinatorics Discrete Mathematics Rings and Algebras 05C15, 05C22, 05C63, 05C75, 20N20 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 $56_{65}$. 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. |
| title | Circular Chromatic Numbers, Balanceability, Relation Algebras, and Network Satisfaction Problems |
| topic | Combinatorics Discrete Mathematics Rings and Algebras 05C15, 05C22, 05C63, 05C75, 20N20 |
| url | https://arxiv.org/abs/2512.06878 |