The Generic Circular Triangle‐Free Graph
Manuel Bodirsky, Santiago Guzmán‐Pro · Journal of Graph Theory · 2025
ABSTRACT In this article, we introduce the generic circular triangle‐free graph and propose a finite axiomatization of its first‐order theory. In particular, our main results show that a countable graph embeds into if and only if it is a ‐free graph. As a byproduct of this result, we obtain a geometric characterisation of finite ‐free graphs, and the (finite) list of minimal obstructions of unit Helly circular‐arc graphs with independence number strictly less than three. The circular chromatic number is a refinement of the classical chromatic number . We construct so that a graph has a circular chromatic number strictly less than three if and only if maps homomorphically to . We build on our main result to show that if and only if can be extended to a ‐free graph, and in turn, we use this result to reprove an old characterisation of due to Brandt (1999). Finally, we answer a question recently asked by Guzmán‐Pro, Hell, and Hernández‐Cruz by showing that the problem of deciding for a given finite graph whether is NP‐complete.