Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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?)


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

DOI: http://dx.doi.org/10.1090/S0002-9947-1979-0530057-2
PII: S 0002-9947(1979)0530057-2
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