Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



The first order theory of $ N$-colorable graphs

Author: William H. Wheeler
Journal: Trans. Amer. Math. Soc. 250 (1979), 289-310
MSC: Primary 03C65; Secondary 03B30, 03C10, 03C35, 05C15
MathSciNet review: 530057
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] C. Berge, Graphs and hypergraphs, North Holland, Amsterdam, 1973. MR 0357172 (50:9640)
  • [2] S. Feferman and R. L. Vaught, The first order properties of products of algebraic systems, Fund. Math. 47 (1959), 57-103. MR 0108455 (21:7171)
  • [3] J. Hirschfeld and W. H. Wheeler, Forcing, arithmetic, division rings, Lecture Notes in Math., vol. 454, Springer-Verlag, Berlin and New York, 1975. MR 0389581 (52:10412)
  • [4] H. J. Keisler, Six classes of theories, J. Austral. Math. Soc. 21 (1976), 257-266. MR 0409168 (53:12930)
  • [5] G. Ringel, Färbungsprobleme auf Flächen und Graphen, VEB Deutscher Verlag der Wissenschaften, Berlin, 1959. MR 0109349 (22:235)
  • [6] A. Robinson, Introduction to model theory and to the metamathematics of algebra, North-Holland, Amsterdam, 1965. MR 0153570 (27:3533)
  • [7] S. Shelah, Stability, the f.c.p., and superstability; model theoretic properties of formulas in first order theory, Ann. Math. Logic 3 (1971), 271-362. MR 0317926 (47:6475)
  • [8] J. R. Shoenfield, Mathematical logic, Addison-Wesley, Reading, Mass., 1967. MR 0225631 (37:1224)
  • [9] W. H. Wheeler, A characterization of companionable, universal theories, J. Symbolic Logic 43 (1978), 402-429. MR 0491131 (58:10400)
  • [10] W. Taylor, Atomic compactness and graph theory, Fund. Math. 65 (1969), 139-145. MR 0246812 (40:81)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 03C65, 03B30, 03C10, 03C35, 05C15

Retrieve articles in all journals with MSC: 03C65, 03B30, 03C10, 03C35, 05C15

Additional Information

Keywords: N-colorable graph, first order theory, model-companion, elimination of quantifiers, $ {\aleph _0}$-categoricity, prime model extension
Article copyright: © Copyright 1979 American Mathematical Society

American Mathematical Society