It is known that every hereditary property can be characterized by finitely many minimal obstructions when restricted to either the class of cographs or the class of $P_4$-reducible graphs. In this work, we prove that also when restricted to the classes of $P_4$-sparse graphs and $P_4$-extendible graphs (both of which extend $P_4$-reducible graphs) every hereditary property can be characterized by finitely many minimal obstructions. We present complete lists of $P_4$-sparse and $P_4$-extendible minimal obstructions for polarity, monopolarity, unipolarity, and $(s,1)$-polarity, where $s$ is a positive integer. In parallel to the case of $P_4$-reducible graphs, all the $P_4$-sparse minimal obstructions for these hereditary properties are cographs.
翻译:众所周知,每个世袭财产的特征都可以有为数不多的最低限度障碍,这些障碍仅限于一类成文法或4美元的可减少图表。在这项工作中,我们证明,在仅限于4美元的剖面图和4美元的可扩展图表(两者均延伸为4美元-可减少的图表)的类别时,每个世袭财产的特征都可以有为数不多的最低限度障碍。我们提供了完整清单,列出4美元的碎块和4美元的可扩大的极性、单极性、1美元-极性、美元为正整数的最低限度障碍。在以4美元的可减少的图表为例的情况下,所有这些世袭财产的最小障碍都是直线式的。