The first order theory of 𝑁-colorable graphs
William Henry Wheeler · Transactions of the American Mathematical Society · 1979
Every N -colorable graph without loops or multiple edges is a substructure of a direct power of a particular, finite, N -coloarable graph. Consequently, the class of N -colorable graphs without loops or endpoints can be recursively axiomatized by a first order, universal Horn theory. This theory has a model-companion which has a primitive recursive elimination of quantifiers and is decidable, complete, ℵ 0 {\aleph _0} -categorical, and independent. The N -colorable graphs without loops or multiple edges which have a proper, prime model extension for the model-companion are precisely the finite, amalgamation bases.