The Generic Circular Triangle-Free Graph

In this article, we introduce the generic circular triangle-free graph C-3 and propose a finite axiomatization of its first-order theory. In particular, our main results show that a countable graph G embeds into C-3 if and only if it is a {K-3,K-1+2K(2),K-1+C-5,C-6}-free graph. As a byproduct of this result, we obtain a geometric characterisation of finite {K-3,K-1+2K(2),K-1+C-5,C-6}-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 chi(c)(G) is a refinement of the classical chromatic number chi(G). We construct C-3 so that a graph G has a circular chromatic number strictly less than three if and only if G maps homomorphically to C-3. We build on our main result to show that chi(c)(G) <3 if and only if G can be extended to a {K-3,K-1+2K(2),K-1+C-5,C-6}-free graph, and in turn, we use this result to reprove an old characterisation of chi(c)(G) <3 due to Brandt (1999). Finally, we answer a question recently asked by Guzm & aacute;n-Pro, Hell, and Hern & aacute;ndez-Cruz by showing that the problem of deciding for a given finite graph G whether chi(c)(G) <3 is NP-complete.