论文标题
遗传图家庭的典型结构。 ii。异国情调的例子
Typical structure of hereditary graph families. II. Exotic examples
论文作者
论文摘要
图$ g $是$ h $ free，如果它不包含诱导子图的同构为$ h $。 ErdőS，Kleitman和Rothschild启动了$ H $ Free Graphs的典型结构的研究，他们已经证明了几乎所有$ C_3 $ Free图都是双分部分。从那时起，已经确定了$ h $ free图的典型结构，用于几个图形$ h $的家庭，包括完整的图形，树木和周期。最近，里德（Reed）和斯科特（Scott）提出了对所有图形$ h $ $ h $ free图的典型结构的猜想描述，该结构扩展了该地区的所有先前已知结果。 我们构建了一个无限的图表，为此，芦苇 - 斯科特猜想失败了，并使用我们在前传论文中开发的方法来描述该家族中$ h $ free Graphs $ h $的典型结构。 使用类似的技术，我们构建了一个无限的图表$ h $，为典型的$ h $ free图中的同质设置的最大尺寸在顶点的数量中是sublinear，回答了Loebl等人的问题。和Kang等。
A graph $G$ is $H$-free if it does not contain an induced subgraph isomorphic to $H$. The study of the typical structure of $H$-free graphs was initiated by Erdős, Kleitman and Rothschild, who have shown that almost all $C_3$-free graphs are bipartite. Since then the typical structure of $H$-free graphs has been determined for several families of graphs $H$, including complete graphs, trees and cycles. Recently, Reed and Scott proposed a conjectural description of the typical structure of $H$-free graphs for all graphs $H$, which extends all previously known results in the area. We construct an infinite family of graphs for which the Reed-Scott conjecture fails, and use the methods we developed in the prequel paper to describe the typical structure of $H$-free graphs for graphs $H$ in this family. Using similar techniques, we construct an infinite family of graphs $H$ for which the maximum size of a homogenous set in a typical $H$-free graph is sublinear in the number of vertices, answering a question of Loebl et al. and Kang et al.
