For any graph , let be the class of graphs with no induced subdivision of . It was conjectured in [A.D. Scott, Induced trees in graphs of large chromatic number, {\em Journal of Graph Theory}, 24:297–311, 1997] that, for every graph , there is a function $f_H: \rightarrow G \in {\rm Forb}^*(H)\chi(G) \leq f_H(\omega(G))H$, namely the paw (a triangle with a pendant edge), the bull (a triangle with two vertex-disjoint pendant edges), and what we call a “necklace,” that is, a graph obtained from a path by choosing a matching such that no edge of the matching is incident with an endpoint of the path, and for each edge of the matching, adding a vertex adjacent to the ends of this edge.

生成讲解博客的中文版本

生成AI智能校验的中文版本