# Oriented Coloring on Recursively Defined Digraphs
## 6 Graph Isomorphism for Oriented Co-Graphs  
The isomorphism problem for undirected co-graphs has been shown to be solvable in polynomial time in [3]. This result can be improved as follows. Two undirected co-graphs \(G_{1}\) and \(G_{1}\) are isomorphic if and only if their canonical co-trees \(T_{1}\) and \(T_{2}\) are isomorphic. A canonical co-tree for a co-graph can be determined in linear time. Thus, by applying a linear time isomorphism test for rooted labeled trees (cf. [25], Section 3.2) on canonical co-trees for \(G_{1}\) and \(G_{2}\), one can decide in linear time whether \(G_{1}\) and \(G_{2}\) are isomorphic. We consider the corresponding problem for oriented co-graphs. **Name**: Oriented Co-Graph Isomorphism (OCI)
**Instance**: Two oriented co-graphs \(G_{1}=(V_{1},A_{1})\) and \(G_{2}=(V_{2},A_{2})\). **Question**: Are \(G_{1}\) and \(G_{2}\) isomorphic, i.e., is there a bijection \(b:V_{1}\to V_{2}\) such that for all \(u,v\in V_{1}\) it holds that \((u,v)\in A_{1}\) if and only if \((b(u),b(v))\in A_{2}\)? For oriented co-graphs, the method using an isomorphism test for rooted labeled trees on the co-trees does not work, since the order of the vertices, which are representing order operations in the di-co-tree, must be preserved. The procedure in Algorithm 2 provides a solution for di-co-trees. Theorem 5: _Let \(G_{1}\) and \(G_{2}\) be two oriented co-graphs, then oriented co-graph isomorphism for \(G_{1}\) and \(G_{2}\) can be solved in linear time._  
Proof: Let \(G_{1}\) and \(G_{2}\) be two oriented cographs with the corresponding di-co-trees \(T_{1}\) and \(T_{2}\), which can be found in linear time with the method of [17]. Moreover we can assume, that the di-co-trees are canonical by Lemma 2. If two graphs are isomorphic, the two canonical di-co-trees must be isomorphic, too. W.l.o.g. assume that the height and the roots of \(T_{1}\) and \(T_{2}\) are equal. Then, if two trees are isomorphic, there must be a bijection from the vertices of \(T_{1}\) of level \(\ell\) to the vertices of \(T_{2}\) of level \(\ell\). We look at the procedure from Algorithm 2. Under the given conditions, the operation of the vertices of level \(\ell\) are either order compositions or disjoint unions for both trees. If the operation on level \(\ell\) is a directed union, the labels of the children of each node on level \(\ell\) are sorted. Otherwise, it is an order composition, where the order of the children cannot be changed, such that the labels of the children will stay in the same order. After visiting every vertex on level \(\ell\), the vectors with the labels of the children are sorted in the sequences \(S_{1}\) and \(S_{2}\). With the method given in [25] (Section 3.2) the sorting can be done in linear time with respect to the number of edges from each vertex to its children. If both sequences are equal, the algorithm continues, since the isomorphism is satisfied for level \(\ell+1\). If it is not, the ordered sequences will be different, such that the algorithm terminates and returns false. This is repeated for every level of both trees, except for level 0, which is the root, where the operations are assumed to be equal, and level \(h\), which is the first level the algorithm goes through. When the leaves on this level are labeled, there is nothing more to do, since these vertices have no children. The isomorphism of level \(h\) is checked on level \(h-1\). Let \(n\) be the number of vertices in \(T_{1}\) and \(T_{2}\) and \(m\) the number of edges. Then, the algorithm needs \(2n\) steps for looking at every vertex of both trees, additional to \(2m\) steps for looking at the children of each vertex. Thus, it runs in linear time.