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
Additional Information
- © Copyright 1979 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 250 (1979), 289-310
- MSC: Primary 03C65; Secondary 03B30, 03C10, 03C35, 05C15
- DOI: https://doi.org/10.1090/S0002-9947-1979-0530057-2
- MathSciNet review: 530057