4 papers
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…
On the Computational Power of Extensional ESO
Manuel Bodirsky, Santiago Guzmán Pro
Extensional ESO is a fragment of existential second-order logic (ESO) that captures the following family of problems. Given a fixed ESO sentence and an input structure $\mathbb…
The Generic Circular Triangle-Free Graph
Manuel Bodirsky, Santiago Guzmán-Pro
In this paper, we introduce the generic circular triangle-free graph and propose a finite axiomatization of its first order theory. In particular, our main results sh…
Forbidden Tournaments and the Orientation Completion Problem
Manuel Bodirsky, Santiago Guzmán-Pro
For a fixed finite set of finite tournaments , the -free orientation problem asks whether a given finite undirected graph has an -free o…