The Generic Circular Triangle-Free Graph

In this paper, we introduce the generic circular triangle-free graph ℂ_3 and propose a finite axiomatization of its first order theory. In particular, our main results show that a countable graph G embeds into ℂ_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 characterization 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 χ_c(G) is a refinement of the classical chromatic number χ(G). We construct ℂ_3 so that a graph G has circular chromatic number strictly less than three if and only if G maps homomorphically to ℂ_3. We build on our main results to show that χ_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 characterization of χ_c(G) < 3 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 G whether χ_c(G) < 3 is NP-complete.