Characterizations for Special Directed Co-graphs

摘要

In this paper we consider special subclasses of directed co-graphs and their characterizations. The class of directed co-graphs has been well-studied by now and there are different definitions and applications. But whereas for undirected co-graphs multiple subclasses have been considered and characterized successfully by several definitions, for directed co-graphs very few known subclasses exist by now. Known classes are oriented co-graphs which we obtain omitting the series composition and which have been analyzed by Lawler in the 1970s and their restriction to linear expressions, recently studied by Boeckner. We consider directed and oriented versions of threshold graphs, simple co-graphs, co-simple co-graphs, trivially perfect graphs, co-trivially perfect graphs, weakly quasi threshold graphs and co-weakly quasi threshold graphs. For all these classes we provide characterizations by finite sets of minimal forbidden induced subdigraphs, which lead to first polynomial time recognition algorithms for the corresponding graph classes. Further, we analyze relations between these graph classes.