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 Free Access

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] Claude Berge, Graphs and hypergraphs, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1973. Translated from the French by Edward Minieka; North-Holland Mathematical Library, Vol. 6. MR 0357172
  • [2] S. Feferman and R. L. Vaught, The first order properties of products of algebraic systems, Fund. Math. 47 (1959), 57–103. MR 0108455
  • [3] Joram Hirschfeld and William H. Wheeler, Forcing, arithmetic, division rings, Lecture Notes in Mathematics, Vol. 454, Springer-Verlag, Berlin-New York, 1975. MR 0389581
  • [4] H. Jerome Keisler, Six classes of theories, J. Austral. Math. Soc. Ser. A 21 (1976), no. 3, 257–266. MR 0409168
  • [5] Gerhard Ringel, Färbungsprobleme auf Flächen und Graphen, Mathematische Monographien, vol. 2, VEB Deutscher Verlag der Wissenschaften, Berlin, 1959 (German). MR 0109349
  • [6] Abraham Robinson, Introduction to model theory and to the metamathematics of algebra, North-Holland Publishing Co., Amsterdam, 1963. MR 0153570
  • [7] 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 0317926
  • [8] Joseph R. Shoenfield, Mathematical logic, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1967. MR 0225631
  • [9] William H. Wheeler, A characterization of companionable, universal theories, J. Symbolic Logic 43 (1978), no. 3, 402–429. MR 0491131
  • [10] Walter Taylor, Atomic compactness and graph theory, Fund. Math. 65 (1969), 139–145. MR 0246812

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