The first order theory of 𝑁-colorable graphs

Wheeler, William H.

doi:10.1090/S0002-9947-1979-0530057-2

The first order theory of $N$-colorable graphs
HTML articles powered by AMS MathViewer

by William H. Wheeler PDF

Trans. Amer. Math. Soc. 250 (1979), 289-310 Request permission

Abstract:

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, ${\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.

References

Claude Berge, Graphs and hypergraphs, North-Holland Mathematical Library, Vol. 6, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1973. Translated from the French by Edward Minieka. MR 0357172
S. Feferman and R. L. Vaught, The first order properties of products of algebraic systems, Fund. Math. 47 (1959), 57–103. MR 108455, DOI 10.4064/fm-47-1-57-103
Joram Hirschfeld and William H. Wheeler, Forcing, arithmetic, division rings, Lecture Notes in Mathematics, Vol. 454, Springer-Verlag, Berlin-New York, 1975. MR 0389581, DOI 10.1007/BFb0064082
H. Jerome Keisler, Six classes of theories, J. Austral. Math. Soc. Ser. A 21 (1976), no. 3, 257–266. MR 409168, DOI 10.1017/s1446788700018541
Gerhard Ringel, Färbungsprobleme auf Flächen und Graphen, Mathematische Monographien, vol. 2, VEB Deutscher Verlag der Wissenschaften, Berlin, 1959 (German). MR 0109349
Abraham Robinson, Introduction to model theory and to the metamathematics of algebra, North-Holland Publishing Co., Amsterdam, 1963. MR 0153570
Saharon Shelah, Stability, the f.c.p., and superstability; model theoretic properties of formulas in first order theory, Ann. Math. Logic 3 (1971), no. 3, 271–362. MR 317926, DOI 10.1016/0003-4843(71)90015-5
Joseph R. Shoenfield, Mathematical logic, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1967. MR 0225631
William H. Wheeler, A characterization of companionable, universal theories, J. Symbolic Logic 43 (1978), no. 3, 402–429. MR 491131, DOI 10.2307/2273518
Walter Taylor, Atomic compactness and graph theory, Fund. Math. 65 (1969), 139–145. MR 246812, DOI 10.4064/fm-65-2-139-145