On characterizations for subclasses of directed co-graphs
- PDF / 787,590 Bytes
- 33 Pages / 439.37 x 666.142 pts Page_size
- 84 Downloads / 180 Views
On characterizations for subclasses of directed co-graphs Frank Gurski1
· Dominique Komander1 · Carolin Rehs1
Accepted: 1 November 2020 © The Author(s) 2020
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 P4 -free graphs (where P4 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 cographs 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 cographs, 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
An extended abstract of this paper appeared in the Proceedings of the International Conference on Combinatorial Optimization and Applications (COCOA 2019; see Gurski et al. 2019a).
B
Frank Gurski [email protected] Dominique Komander [email protected] Carolin Rehs [email protected]
1
Institute of Computer Science, Algorithmics for Hard Problems Group, University of Düsseldorf, 40225 Düsseldorf, Germany
123
Journal of Combinatorial Optimization
1 Introduction During the last years classes of directed graphs have received a lot of attention (BangJensen and Gutin 2018) since they are useful in multiple applications of directed networks. For instance the class of directed co-graphs can be used in applications in the field of genetics (see Nojgaard et al. 2018). However, the field of directed co-graphs is far less well studied than the undirected version, although it has a similarly useful structure. There are multiple subclasses of undirected co-graphs which are already characterized successfully by several definitions. Among these are trivially perfect graphs (Golumbic 1978), threshold graphs (Chvátal and Hammer 1977), weakly quasi threshold graphs (Bapat et al. 2008; Nikolopoulos and Papadopoulos 2011), and simple co-graphs (Heggernes et al. 2011), see Table 2. Moreover, there are also corresponding subclasses of
Data Loading...
