Submission date: 18 April 2024

Abstract:

In this paper, 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 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 C_3 so that a graph G has circular chromatic number strictly less than three if and only if G maps homomorphically to C_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.

Mathematics Subject Classification: 05C15, 05C63, 05C62, 05C75, 03C10, 03C35

Keywords and phrases:

Full text arXiv 2404.12082: pdf, ps.