On unavoidable‐induced subgraphs in large prime graphs. Issue 2 (15th November 2017)

• Record Type: Journal Article
• Authors: Malliaris, M.; Terry, C.
• Is Part Of: Journal of graph theory. Volume 88:Issue 2(2018)
• Page Start: 255
• Page End: 270
• Publication Date: 2017-11-15
• Subjects: model theory -- prime graph -- Ramsey -- stable graph; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22209
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: Chudnovsky, Kim, Oum, and Seymour recently established that any prime graph contains one of a short list of induced prime subgraphs [1]. In the present article, we reprove their theorem using many of the same ideas, but with the key model‐theoretic ingredient of first determining the so‐called amount of stability of the graph. This approach changes the applicable Ramsey theorem, improves the bounds and offers a different structural perspective on the graphs in question. Complementing this, we give an infinitary proof that implies the finite result.