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)



$K_ {l+1}$-free graphs: asymptotic structure and a $0$-$1$ law

Authors: Ph. G. Kolaitis, H. J. Prömel and B. L. Rothschild
Journal: Trans. Amer. Math. Soc. 303 (1987), 637-671
MSC: Primary 05C15; Secondary 03C13
MathSciNet review: 902790
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The structure of labeled ${K_{l + 1}}$-free graphs is investigated asymptotically. Through a series of stages of successive refinement the structure of "almost all" such graphs is found sufficiently precisely to prove that they are in fact $l$-colorable ($l$-partite). With the asymptotic information obtained it is shown also that in the class of ${K_{l + 1}}$-free graphs there is a first-order labeled $0$-$1$ law. With this result, and those cases already known, we can say that any infinite class of finite undirected graphs with amalgamations, induced subgraphs and isomorphisms has a $0$-$1$ law.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C15, 03C13

Retrieve articles in all journals with MSC: 05C15, 03C13

Additional Information

Article copyright: © Copyright 1987 American Mathematical Society