Unavoidable induced subgraphs in large graphs with no homogeneous sets

详细信息    查看全文

• 作者：Maria Chudnovsky^a ; ^{mchudnov@math.princeton.edu" class="auth_mail" title="E-mail the corresponding author} ; Ringi Kim^a ; ^{ringikim@princeton.edu" class="auth_mail" title="E-mail the corresponding author} ; Sang-il Oum^b ; ^{sangil@kaist.edu" class="auth_mail" title="E-mail the corresponding author} ; Paul Seymour^a ; ^{pds@math.princeton.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Modular decomposition ; Induced subgraph ; Prime graph ; Ramsey
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2016
• 出版时间：May 2016
• 年：2016
• 卷：118
• 期：Complete
• 页码：1-12
• 全文大小：377 K

文摘

A homogeneous set of an n-vertex graph is a set X   of vertices (2≤|X|≤n−1$2\le |X|\le n-1$) such that every vertex not in X is either complete or anticomplete to X. A graph is called prime if it has no homogeneous set. A chain of length t   is a sequence of t+1$t+1$ vertices such that for every vertex in the sequence except the first one, its immediate predecessor is its unique neighbor or its unique non-neighbor among all of its predecessors. We prove that for all n, there exists N such that every prime graph with at least N   vertices contains one of the following graphs or their complements as an induced subgraph: (1) the graph obtained from K_1,n$K_{1,n}$ by subdividing every edge once, (2) the line graph of K_2,n$K_{2,n}$, (3) the line graph of the graph in (1), (4) the half-graph of height n, (5) a prime graph induced by a chain of length n, (6) two particular graphs obtained from the half-graph of height n by making one side a clique and adding one vertex.