Generalizing Cographs to 2-Cographs

DOI10.37236/10272MaRDI QIDQ6361722arXivFDO

Authors James Oxley, Jagdeep Singh

Publication date 28 February 2021

Published in arXiv

Full work available at URL https://doi.org/10.37236/10272

Mathematics Subject Classification ID

Connectivity (05C40) Graph minors (05C83)

arXiv classification

math.CO

Abstract: A graph in which every connected induced subgraph has a disconnected complement is called a cograph. Such graphs are precisely the graphs that do not have the 4-vertex path as an induced subgraph. We define a $2$-cograph to be a graph in which the complement of every $2$-connected induced subgraph is not $2$-connected. We show that, like cographs, $2$-cographs can be recursively defined. But, unlike cographs, $2$-cographs are closed under induced minors. We characterize the class of non-$2$-cographs for which every proper induced minor is a $2$-cograph. We further find the finitely many members of this class whose complements are also induced-minor-minimal non-$2$-cographs.

This page was built for publication: Generalizing Cographs to 2-Cographs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6361722)