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

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 the same is true when restricted to some other superclasses of cographs, including...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2024-05, Vol.40 (3), Article 53
Main Authors: Contreras-Mendoza, Fernando Esteban, Hernández-Cruz, César
Format: Article
Language:English
Subjects:
Combinatorics
Engineering Design
Graphs
Mathematics
Mathematics and Statistics
Obstructions
Original Paper
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 the same is true when restricted to some other superclasses of cographs, including P 4 -sparse and P 4 -extendible graphs (both of which extend P 4 -reducible graphs). We also 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.
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-024-02784-7