The Generic Circular Triangle-Free Graph

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