1 Introduction
2 Preliminaries
2.1 Notations for undirected graphs
2.2 Notations for directed graphs
-
one of the arcs (u, v) and (v, u), we denote D as an orientation of G. Every digraph D that can be obtained by an orientation of an undirected graph G is called an oriented graph.
-
one or both of the arcs (u, v) and (v, u), we denote D as a biorientation of G. A digraph D that we get by a biorientation of an undirected graph G is called a bioriented graph.
-
both arcs (u, v) and (v, u), we denote D as a complete biorientation of G. Since in this case D is well defined by G we also denote it by \(\overleftrightarrow {G}\). A digraph D that we obtain by a complete biorientation of an undirected graph G is called a complete bioriented graph.
2.3 Induced subgraph characterizations for hereditary classes
3 Undirected co-graphs and subclasses
-
The disjoint union of \(G_1\) and \(G_2\), denoted by \(G_1\oplus G_2\), is the graph with vertex set \(V_1\cup V_2\) and edge set \(E_1\cup E_2\).
-
The join of \(G_1\) and \(G_2\), denoted by \(G_1\otimes G_2\), is the graph with vertex set \(V_1\cup V_2\) and edge set \(E_1\cup E_2 \cup \{\{v_1,v_2\}~|~ v_1\in V_1, v_2\in V_2\}\).
3.1 Co-graphs
3.2 Subclasses of co-graphs
Class X | Notation | Operations | \({\text {Forb}}(X)\) | ||
---|---|---|---|---|---|
Co-graphs | \({\text {C}}\) | \(\bullet \) | \(G_1\oplus G_2\) | \(G_1\otimes G_2\) | \(P_4\) |
quasi threshold/trivially perfect graphs | \({\text {TP}}\) | \(\bullet \) | \(G_1\oplus G_2\) | \(G_1 \otimes \bullet \) | \(P_4\), \(C_4\) |
Co-quasi threshold/co-trivially perfect graphs | \({\text {CTP}}\) | \(\bullet \) | \(G_1 \oplus \bullet \) | \(G_1\otimes G_2\) | \(P_4\), \(2K_2\) |
Threshold graphs | \({\text {T}}\) | \(\bullet \) | \(G_1\oplus \bullet \) | \(G_1 \otimes \bullet \) | \(P_4\), \(C_4\), \(2K_2\) |
Simple co-graphs | \({\text {SC}}\) | \(\bullet \) | \(G_1\oplus I\) | \(G_1 \otimes I\) | \(P_4\), co-\(2P_3\), \(2K_2\) |
Co-simple co-graphs | \({\text {CSC}}\) | \(\bullet \) | \(G_1\oplus K\) | \(G_1 \otimes K\) | \(P_4\), \(2P_3\), \(C_4\) |
Weakly quasi threshold graphs | \({\text {WQT}}\) | I | \(G_1\oplus G_2\) | \(G_1 \otimes I\) | \(P_4\), co-\(2P_3\) |
Co-weakly quasi threshold graphs | \({\text {CWQT}}\) | K | \(G_1\oplus K\) | \(G_1\otimes G_2\) | \(P_4\), \(2P_3\) |
3.3 Relations
4 Directed co-graphs and subclasses
-
The disjoint union of \(G_1\) and \(G_2\), denoted by \(G_1 \oplus G_2\), is the digraph with vertex set \(V_1 \cup V_2\) and arc set \(E_1\cup E_2\).
-
The series composition of \(G_1\) and \(G_2\), denoted by \(G_1\otimes G_2\), is the digraph with vertex set \(V_1 \cup V_2\) and arc set \(E_1\cup E_2\cup \{(u,v),(v,u)~|~u\in V_1, v\in V_2\}\).
-
The order composition of \(G_1\) and \(G_2\), denoted by \(G_1\oslash G_2\), is the digraph with vertex set \(V_1 \cup V_2\) and arc set \(E_1\cup E_2\cup \{(u,v)~|~u\in V_1, v\in V_2\}\).
4.1 Directed co-graphs
4.2 Oriented co-graphs
4.3 Series-parallel partial order digraphs
-
Let \((X_1 ,\le )\) and \((X_2 , \le )\) be two disjoint series-parallel partial orders, then distinct elements \(x,y \in X_1 \cup X_2\) of a series composition6 have the same order they have in \(X_1\) or \(X_2\). Respectively, this holds if both of them are from the same set, and \(x \le y\) if \(x \in X_1\) and \(y \in X_2\).
-
Two elements \(x, y \in X_1 \cup X_2\) of a parallel composition are comparable if and only if both of them are in \(X_1\) or both in \(X_2\), while they keep their corresponding order.
-
Symmetric part Exchange each order composition with a directed union composition. Since there are no more oriented arcs left, this tree represents a co-graph.
-
Asymmetric part Exchange each series composition with a directed union composition. Since there are no more bidirectional edges left, this tree represents an oriented co-graph, e.g. a series-parallel partial order digraph.
4.4 Directed trivially perfect graphs
4.5 Oriented trivially perfect graphs
4.6 Directed weakly quasi threshold graphs
\(Q_1 = Y_2 \otimes Y_2\)
|
\(Q_2 = Y_1 \oslash Y_1\)
|
\(Q_3 = Y_3 \otimes Y_3\)
|
\(Q_4 = Y_2 \otimes Y_3\)
|
\(Q_5 = Y_1 \oslash Y_4\)
|
\(Q_6 = Y_4 \oslash Y_1\)
|
\(Q_7 = Y_4 \oslash Y_4\)
|
4.7 Oriented weakly quasi threshold graphs
4.8 Directed co-weakly quasi threshold graphs
4.9 Oriented co-weakly quasi threshold graphs
4.10 Directed simple co-graphs
4.11 Oriented simple co-graphs
4.12 Directed co-simple co-graphs
4.13 Oriented co-simple co-graphs
4.14 Directed threshold graphs
-
\(t_i=3\) if v(i) is a bi-dominating vertex for the graph \(G[\{v(1),\ldots ,v(i)\}]\)\(t_i=2\) if v(i) is a in-dominating vertex for the graph \(G[\{v(1),\ldots ,v(i)\}]\)
-
\(t_i=1\) if v(i) is a out-dominating vertex for the graph \(G[\{v(1),\ldots ,v(i)\}]\) and
-
\(t_i=0\) if v(i) is an isolated vertex for the graph \(G[\{v(1),\ldots ,v(i)\}]\).
4.15 Oriented threshold graphs
4.16 Threshold digraphs and Ferres digraphs
4.17 Overview
class X | notation | operations | \({\text {Forb}}(X)\) | ||||
---|---|---|---|---|---|---|---|
directed co-graphs | \({\text {DC}}\) | \(\bullet \) | \(G_1\oplus G_2\) | \(G_1\oslash G_2\) | \(G_1\otimes G_2\) | \(D_1, \dots , D_8\) | |
oriented co-graphs | \({\text {OC}}\) | \(\bullet \) | \(G_1\oplus G_2\) | \(G_1\oslash G_2\) | \(D_1, D_5, D_8, \overleftrightarrow {K_2}\) | ||
directed trivially perfect | \({\text {DTP}}\) | \(\bullet \) | \(G_1\oplus G_2\) | \(G_1 \oslash \bullet \) | \(\bullet \oslash G_2\) | \(G_1 \otimes \bullet \) | \(D_1, \dots ,D_{15}\) |
oriented trivially perfect | \({\text {OTP}}\) | \(\bullet \) | \(G_1\oplus G_2\) | \(G_1 \oslash \bullet \) | \(\bullet \oslash G_2\) | \(D_1,D_5,D_8,\overleftrightarrow {K_2},D_{12}\) | |
directed co-trivially perfect | \({\text {DCTP}}\) | \(\bullet \) | \(G_1 \oplus \bullet \) | \(G_1 \oslash \bullet \) | \(\bullet \oslash G_2\) | \(G_1\otimes G_2\) | \(D_1, \dots ,D_{8}\), \(D_{12}, \dots ,D_{15}\) |
\({\text {co-}}D_{11},{\text {co-}}D_{10},{\text {co-}}D_9\) | |||||||
oriented co-trivially perfect \(*\) | \({\text {OCTP}}\) | \(\bullet \) | \(G_1 \oplus \bullet \) | \(G_1 \oslash \bullet \) | \(\bullet \oslash G_2\) | \(D_1, D_5, D_8, D_{12},{\text {co-}}D_{11}, \overleftrightarrow {K_2}\) | |
directed weakly quasi threshold | \({\text {DWQT}}\) | I | \(G_1\oplus G_2\) | \(G_1 \oslash I\) | \(I \oslash G_2\) | \(G_1 \otimes I\) | \(D_1,\ldots ,D_8, Q_1,\ldots ,Q_7\) |
oriented weakly quasi threshold | \({\text {OWQT}}\) | I | \(G_1\oplus G_2\) | \(G_1 \oslash I\) | \(I \oslash G_2\) | \(D_1,D_5,D_8, \overleftrightarrow {K_2},Q_7\) | |
directed co-weakly quasi thresh. | \({\text {DCWQT}}\) | K | \(G_1 \oplus K\) | \(G_1 \oslash K\) | \(K \oslash G_2\) | \(G_1\otimes G_2\) | \(D_1,\,D_8,{\text {co-}}Q_1,\ldots ,{\text {co-}}Q_7\) |
oriented co-weakly quasi threshold | \({\text {OCWQT}}\) | T | \(G_1 \oplus T\) | \(G_1 \oslash T\) | \(T \oslash G_2\) | \(D_1,D_5,D_8, \overleftrightarrow {K_2},\) | |
\(D_{12}, D_{21},D_{22},D_{23} \) | |||||||
directed simple co-graphs | \({\text {DSC}}\) | \(\bullet \) | \(G_1\oplus I\) | \(G_1 \oslash I\) | \(I \oslash G_2\) | \(G_1 \otimes I\) | \(D_1,\ldots ,D_8,Q_1,\ldots ,Q_7,\) |
\({\text {co-}}D_9, {\text {co-}}D_{10}, {\text {co-}}D_{11}\) | |||||||
oriented simple co-graphs | \({\text {OSC}}\) | \(\bullet \) | \(G_1\oplus I\) | \(G_1 \oslash I\) | \(I \oslash G_2\) | \(D_1,D_5,D_8, \overleftrightarrow {K_2},Q_7, {\text {co-}}D_{11}\) | |
directed co-simple co-graphs | \({\text {DCSC}}\) | \(\bullet \) | \(G_1\oplus K\) | \(G_1 \oslash K\) | \(K \oslash G_2\) | \(G_1 \otimes K\) | \(D_1,\ldots ,D_8,Q_1,\) |
\({\text {co-}}Q_1,\ldots ,{\text {co-}}Q_7, D_{9}, D_{10}\) | |||||||
oriented co-simple co-graphs | \({\text {OCSC}}\) | \(\bullet \) | \(G_1\oplus T\) | \(G_1 \oslash T\) | \(T \oslash G_2\) | \(D_1,D_5,D_8, \overleftrightarrow {K_2},\) | |
\(D_{12}, D_{21}, D_{22}, D_{23}\) | |||||||
directed threshold graphs | \({\text {DT}}\) | \(\bullet \) | \(G_1 \oplus \bullet \) | \(G_1 \oslash \bullet \) | \(\bullet \oslash G_2\) | \(G_1 \otimes \bullet \) | \(D_1, \dots ,D_{15}\) |
\({\text {co-}}D_{11},{\text {co-}}D_{10},{\text {co-}}D_9\) | |||||||
oriented threshold graphs \(*\) | \({\text {OT}}\) | \(\bullet \) | \(G_1 \oplus \bullet \) | \(G_1 \oslash \bullet \) | \(\bullet \oslash G_2\) | \(D_1,D_5,D_8,\overleftrightarrow {K_2},D_{12},{\text {co-}}D_{11}\) |