On characterizations for subclasses of directed co-graphs

Frank Gurski (), Dominique Komander () and Carolin Rehs ()
Additional contact information
Frank Gurski: University of Düsseldorf
Dominique Komander: University of Düsseldorf
Carolin Rehs: University of Düsseldorf

Journal of Combinatorial Optimization, 2021, vol. 41, issue 1, No 15, 234-266

Abstract: Abstract Undirected co-graphs are those graphs which can be generated from the single vertex graph by disjoint union and join operations. Co-graphs are exactly the $$P_4$$ P 4 -free graphs (where $$P_4$$ P 4 denotes the path on 4 vertices). The class of co-graphs itself and several subclasses haven been intensively studied. Among these are trivially perfect graphs, threshold graphs, weakly quasi threshold graphs, and simple co-graphs. Directed co-graphs are digraphs which can be defined by, starting with the single vertex graph, applying the disjoint union, order composition, and series composition. By omitting the series composition we obtain the subclass of oriented co-graphs which has been analyzed by Lawler in the 1970s. The restriction to linear expressions was recently studied by Boeckner. Until now, there are only a few versions of subclasses of directed co-graphs. By transmitting the restrictions of undirected subclasses to the directed classes, we define the corresponding subclasses for directed co-graphs. 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 give characterizations by finite sets of minimal forbidden induced subdigraphs. Additionally, we analyze the relations between these graph classes.

Keywords: Co-graphs; Directed co-graphs; Directed threshold graphs; Digraphs; Threshold graphs; Forbidden induced subdigraph characterizations (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00670-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:41:y:2021:i:1:d:10.1007_s10878-020-00670-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00670-5

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().