Minimal Obstructions for Polarity, Monopolarity, Unipolarity and (s, 1)-Polarity in Generalizations of Cographs

期刊论文
出版模式：

开放获取
发表日期：

2024年4月9日

查看全文

Fernando Esteban Contreras-Mendoza,
César Hernández-Cruz

摘要

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$ $P_{4}$ -reducible graphs. In this work, we prove that the same is true when restricted to some other superclasses of cographs, including $P_4$ $P_{4}$ -sparse and $P_4$ $P_{4}$ -extendible graphs (both of which extend $P_4$ $P_{4}$ -reducible graphs). We also present complete lists of $P_4$ $P_{4}$ -sparse and $P_4$ $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$ $P_{4}$ -reducible graphs, all the $P_4$ $P_{4}$ -sparse minimal obstructions for these hereditary properties are cographs.