加载中…
Chudnovsky, Cook, Davies, and Oum introduced the notion of Pollyanna graph classes: a class is Pollyanna if for every -bounded class , the intersection is polynomially -bounded. They further defined to be strongly Pollyanna if it is -strongly Pollyanna for some integer , meaning that is polynomially -bounded for every -good class . They asked whether there are Pollyanna graph classes that are not strongly Pollyanna. In this note we answer this question affirmatively, under the literal interpretation that graph classes are not required to be hereditary. We construct a class that is Pollyanna but, for every , is not -strongly Pollyanna; in particular is not strongly Pollyanna.

生成讲解博客的中文版本

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