Oriented Vertex and Arc Coloring of Edge Series-Parallel Digraphs

Abstract

We study the oriented vertex and arc coloring problem on edge series-parallel digraphs which are related to the well known series-parallel graphs. The oriented class of edge series-parallel digraphs is recursively defined from pairs of vertices connected by a single arc and applying the parallel and series composition, which leads to specific orientations of undirected series-parallel graphs. We re-prove the known bound of 7 for the oriented chromatic number and the oriented chromatic index of series-parallel digraphs and we show that these bounds are tight even for edge series-parallel digraphs. Further, we give linear time solutions for computing the oriented chromatic number and the oriented chromatic index of minimal series-parallel digraphs and edge series-parallel digraphs.

1 Introduction and Preliminaries

In this paper we consider graph colorings for oriented graphs, i.e. digraphs with no loops and no opposite arcs.

Courcelle introduced oriented vertex colorings [2], in particular an oriented r-vertex-coloring of an oriented graph $G=(V,E)$ is a mapping $c:V\rightarrow \{1,\ldots ,r\}$ such that:

• $c(u)\ne c(v)$ for every $(u,v)\in E$,

• $c(u)\ne c(y)$ for every $(u,v)\in E$ and $(x,y)\in E$ with $c(v)=c(x)$.

The oriented chromatic number of G, denoted by $\chi _o(G)$, is the smallest r such that there exists an oriented r-vertex-coloring for G.

An oriented r-vertex-coloring of an oriented graph G corresponds to an oriented graph H on r vertices, such that there exists a homomorphism from G to H. We then call H the color graph of G.

In the oriented chromatic number problem ($\text {OCN}$) there is given an oriented graph G and an integer r and one has to decide whether there is an oriented r-vertex-coloring for G. If r is not part of the input, we call the related problem the r-Oriented Chromatic Number ($\text {OCN}_{r}$). If $r\le 3$, we can decide $\text {OCN}_{r}$ in polynomial time, while $\text {OCN}_{4}$ is still NP-complete [5]. Further, for every transitive acyclic digraph and every minimal series-parallel digraph $\text {OCN}$ can be solved in linear time [3].

An oriented r-arc-coloring of an oriented graph $G=(V,E)$ is a mapping $c:E\rightarrow \{1,\ldots ,r\}$ such that:

• $c((u,v))\ne c((v,w))$ for every two arcs $(u,v)\in E$ and $(v,w)\in E$

• $c((u,v))\ne c((y,z))$ for every four arcs $(u,v)\in E$, $(v,w)\in E$, $(x,y)\in E$, and $(y,z)\in E$, with $c((v,w))=c((x,y))$.

Moreover, the oriented chromatic index of G, denoted by $\chi '_o(G)$, is the smallest r such that G has an oriented r-arc-coloring.

In the oriented chromatic index problem ($\text {OCI}$) we have an oriented graph G and an integer r and we need to decide whether there is an oriented r-arc-coloring for G. If r is not part of the input, we call the related problem the r-Oriented Chromatic Index ($\text {OCI}_{r}$). If $r\le 3$, then we can decide $\text {OCI}_{r}$ in polynomial time, while $\text {OCI}_{4}$ is NP-complete [6].

The line digraph LD(G) of digraph G has a vertex for every arc in G and an arc from u to v if and only if $u=(x,y)$ and $v=(y,z)$ for vertices x, y, z from G [4]. We call digraph G the root digraph of LD(G).

Observation 1

([6]). Let G be an oriented graph. Then, it holds that

• 1. $\chi '_o(G) = \chi _o(LD(G))$ and

• 2. $\chi '_o(G)\le \chi _o(G)$

The definition of oriented vertex-coloring and oriented arc-coloring was often used for undirected graphs, where the maximum value $\chi _o(G')$ or $\chi '_o(G')$ of all possible orientations $G'$ of a graph G is considered. In this sense it has been shown in [8] that every series-parallel graph has oriented chromatic number at most 7 and that this bound is tight. Further, due [7] every series-parallel graph has oriented chromatic index at most 7, this bound is also tight. These results lead to (not necessarily tight) upper bounds for the oriented chromatic number and the oriented chromatic index of edge series-parallel digraphs.

In this paper we re-prove the bound of 7 for the oriented chromatic index (Corollary 3) and the oriented chromatic number (Theorem 2) of edge series-parallel digraphs and we show that these bounds are tight even for edge series-parallel digraphs (Expressions $X_3$ and $X_4$). Furthermore, we give linear time solutions for computing the oriented chromatic index (Theorem 1) and the oriented chromatic number (Theorem 3) of edge series-parallel digraphs.

2 Minimal Vertex Series-Parallel Digraphs

We recall the definition of minimal vertex series-parallel digraphs.

Definition 1

(Minimal Vertex Series-Parallel Digraphs [9]). The class of minimal vertex series-parallel digraphs, msp-digraphs for short, is recursively defined as follows.

• (i) Every digraph on a single vertex $(\{v\},\emptyset )$, denoted by v, is a minimal vertex series-parallel digraph.

• (ii) If $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ are vertex-disjoint minimal vertex series-parallel digraphs and $O_1$ is the set of vertex of outdegree 0 (set of sinks) in $G_1$ and $I_2$ is the set of vertices of indegree 0 (set of sources) in $G_2$, then

  • (a) the parallel composition $G_1 \cup G_2 =(V_1\cup \,V_2, E_1\cup \,E_2)$ is a minimal vertex series-parallel digraph and

  • (b) the series composition $G_1 \times G_2=(V_1\cup V_2,E_1\cup E_2\cup (O_1 \times I_2))$ is a minimal vertex series-parallel digraph.

An expression X using the operations of Definition 1 is called an msp-expression while $\text {digraph}(X)$ is the digraph defined in X.

Using the recursive structure of msp-digraphs in [3] we show the following bound.

Proposition 1

([3]). Let G be an msp-digraph. Then, it holds that $\chi _o(G)\le 7$.

We can also bound the oriented chromatic number of an msp-digraph G using the corresponding root digraph $G'$ which is an esp-digraph (see Sect. 3). By Lemma 1, Observation 1(1.), and Corollary 3 it holds that $\chi _o(G)=\chi _o(LD(G')) = \chi '_o(G') \le 7$.

For the optimality of the shown bound, we recall from [3] the msp-expression

$$\begin{aligned} \begin{aligned} X_1 =&v_{1} \times (v_2 \cup v_3 \times (v_4 \cup v_5 \times v_6))\times (v_7 \cup (v_8 \cup v_9 \times v_{10})\\&\times (v_{11} \cup v_{12} \times v_{13}))\times (v_{14}\cup (v_{15} \cup (v_{16} \cup v_{17} \times v_{18})\\&\times (v_{19} \cup v_{20} \times v_{21}))\times (v_{22} \cup (v_{23} \cup v_{24} \times v_{25})\times v_{26}) )\times v_{27}. \end{aligned} \end{aligned}$$

Since $\chi _o(\text {digraph}(X_1))=7$ the bound of Proposition 1 is best possible.

Proposition 2

([3]). Let G be an msp-digraph. Then, the oriented chromatic number of G can be computed in linear time.

By Proposition 1 and Observation 1(2.) we know the following bound.

Corollary 1

Let G be an msp-digraph. Then, it holds that $\chi '_o(G)\le 7$.

For the optimality of the shown bound we recursively define msp-expressions $Y_i$. $Y_0$ defines a single vertex graph and for $i\ge 1$ we define $Y_i= (Y_0 \cup Y_{i-1} \times Y_{i-1})$ in order to define $X_2= Y_0 \times Y_0 \times Y_6 \times Y_0 \times Y_0$. Since $\chi '_o(\text {digraph}(X_2))=7$, which was computed by a computer program, we know that that the bound of Corollary 1 is best possible.

3 Edge Series-Parallel Digraphs

Undirected series-parallel graphs are graphs with two distinguished vertices called terminals, formed recursively by parallel and series composition [1, Section 11.2].

Proposition 3

([8]). Let $G'$ be an orientation of a series-parallel graph G. Then, it holds that $\chi _o(G')\le 7$.

In [8] it was also shown that the bound is tight. For the chromatic index of orientations of undirected series-parallel graphs Observation 1(2.) and Proposition 3 lead to the following bound.

Corollary 2

Let $G'$ be some orientation of a series-parallel graph G. Then, it holds that $\chi '_o(G')\le 7$.

In [7] it was shown that the bound is tight.

We recall the definition of edge series-parallel digraphs, originally defined as edge series-parallel multidigraphs.

Definition 2

(Edge Series-Parallel Multidigraphs [9]). The class of edge series-parallel multidigraphs, esp-digraphs for short, is recursively defined as follows.

• (i) Every digraph of two distinct vertices joined by a single arc $(\{u,v\},\{(u,v)\})$, denoted by (u, v), is an edge series-parallel multidigraph.

• (ii) If $G_1=(V_1,A_1)$ and $G_2=(V_2,A_2)$ are vertex-disjoint minimal edge series-parallel multidigraphs, then

  • (a) the parallel composition $G_1\cup G_2$, which identifies the source of $G_1$ with the source of $G_2$ and the sink of $G_1$ with the sink of $G_2$, is an edge series-parallel multidigraph and

  • (b) the series composition $G_1\times G_2$, which identifies the sink of $G_1$ with the source of $G_2$, is an edge series-parallel multidigraph.

An expression X using the operations of Definition 2 is called an esp-expression and $\text {digraph}(X)$ the defined digraph.

Lemma 1

([9]). An acyclic multidigraph G with a single source and a single sink is an esp-digraph if and only if LD(G) is an msp-digraph.

Oriented Arc-Colorings. Since every esp-digraph is an orientation of a series-parallel graph by Corollary 2 we get the following bound.

Corollary 3

Let G be an esp-digraph. Then, it holds that $\chi '_o(G)\le 7$.

We can also bound the oriented chromatic index of an esp-digraph G using the corresponding line digraph LD(G) which is an msp-digraph. Then, by Observation 1(1.), Lemma 1 and Proposition 1 it holds that $\chi '_o(G)= \chi _o(LD(G)) \le 7$.

The results of [7] even show that 7 is a tight upper bound for the oriented chromatic index of every orientation of series-parallel graphs. In order to show that this bound is also tight for the subclass of esp-digraphs, we use the esp-expression

$$\begin{aligned} \begin{aligned} X_3 =&(v_{1},v_2) \times ((v_2,v_5) \cup (v_2,v_3) \times ((v_3,v_5) \cup (v_3,v_4) \times (v_4,v_5)))\\&\times \, ((v_5,v_9) \cup ((v_5,v_7) \cup (v_5,v_6) \times (v_{6},v_7))\times ((v_{7},v_9) \cup (v_{7},v_8) \\&\times \,(v_{8},v_9)))\times ((v_9,v_{16})\cup ((v_9,v_{13}) \cup ((v_9,v_{11}) \cup (v_9,v_{10}) \\&\times \,(v_{10},v_{11}))\times ((v_{11},v_{13}) \cup (v_{11},v_{12}) \times (v_{12},v_{13})))\times ((v_{13},v_{16}) \\&\cup \,((v_{13},v_{15}) \cup (v_{13},v_{14}) \times (v_{14},v_{15}))\times (v_{15},v_{16})) )\times (v_{16},v_{17}). \end{aligned} \end{aligned}$$

Since $\chi '_o(\text {digraph}(X_3))=\chi _o(LD(\text {digraph}(X_3)))= \chi _o(\text {digraph}(X_1))= 7$, where $X_1$ is defined in Sect. 2, it holds that the bound of Corollary 3 is best possible.

By Proposition 2 and Observation 1(1.) we obtain the following result.

Theorem 1

Let G be an esp-digraph. Then, the oriented chromatic index of G can be computed in linear time.

Oriented Vertex Colorings. Since every esp-digraph is an orientation of a series-parallel graph by Proposition 3 we have the following bound.

Corollary 4

Let G be an esp-digraph. Then, it holds that $\chi _o(G)\le 7$.

The proof of Proposition 3 given in [8] uses the color graph $H=(V_H,E_H)$ where $V_H=\{1,2,3,4,5,6,7\}$ and $E_H=\{(i,j)\mid j-i \equiv 1, 2, \text { or } 4 ~(\bmod ~7) \}$ which is built from the non-zero quadratic residues of 7. Next, we give an alternative proof of Corollary 4 using the recursive structure of esp-digraphs.

Theorem 2

Let G be some esp-digraph. Then, it holds that $\chi _o(G)\le 7$.

Proof

Let $G=(V_G,E_G)$ be some esp-digraph. We use the color graph H built from the non-zero quadratic residues of 7 defined above to define an oriented 7-vertex-coloring $c:V_G\rightarrow \{1,\ldots ,7\}$ for G.

First, we color the source of G by 1 and the sink of G by 2. Next, we recursively decompose G in order to color all vertices of G. In any step we keep the invariant that $(c(q),c(s))\in E_H$, if q is the source of G and s is the sink of G.

• If G emerges from parallel composition $G_1 \cup G_2$, we proceed with coloring $G_1$ and $G_2$ on its own. Doing so, the color of the source and sink in $G_1$ and $G_2$ do not change.

• If G emerges from series composition $G_1 \times G_2$, let a be the color of the source and c be the color of the sink in G. For the sink of $G_1$ and the source of $G_2$ we choose color b, such that the arcs (a, b) and (b, c) are in color graph H.

• If G consists of a pair of vertices connected by a single arc, the coloring is given by our invariant.   $\square$

In order to verify the optimality of the shown bound, we consider the esp-expression

$$\begin{aligned} \begin{aligned} X_4 =&((v_1,v_4)\cup ((v_1,v_2)\times ((v_2,v_4)\cup ((v_2,v_3)\times (v_3,v_4))))) \\&\times ((((v_4,v_6)\cup ((v_4,v_5)\times (v_5,v_6))) \times (v_6,v_7))\cup (v_4,v_7)). \end{aligned} \end{aligned}$$

Since $\chi _o(\text {digraph}(X_4))=7$ the bound of Theorem 2 is best possible.

In order to compute the oriented chromatic number of an esp-digraph $G=(V,E)$ defined by an esp-expression X, we recursively compute the set F(X) of all triples $(H,\ell ,r)$ such that H is a color graph for G, where $\ell$ and r are the colors of the source and sink, respectively, in G with respect to the coloring by H. By Theorem 2 and also by Corollary 4 we can conclude that .

For two color graphs $H_1=(V_1,E_1)$ and $H_2=(V_2,E_2)$ we define $H_1+H_2=(V_1\cup V_2,E_1\cup E_2)$.

Lemma 2

• 1. For every $(u,v)\in E$ it holds that $F((u,v))=\{((\{i,j\},\{(i,j)\} ),i,j)~|~ 1\le i,j \le 7,~ i\ne j\}$.

• 2. For every two esp-expressions $X_1$ and $X_2$ we obtain $F(X_1\cup X_2)$ from $F(X_1)$ and $F(X_2)$ as follows. For every $(H_1,\ell _1,r_1) \in F(X_1)$ and every $(H_2,\ell _2,r_2) \in F(X_2)$ such that graph $H_1+H_2$ is oriented, $\ell _1=\ell _2$, and $r_1=r_2$, we put $(H_1 + H_2,\ell _1,r_1)$ into $F(X_1\cup X_2)$.

• 3. For every two esp-expressions $X_1$ and $X_2$ we obtain $F(X_1\times X_2)$ from $F(X_1)$ and $F(X_2)$ as follows. For every $(H_1,\ell _1,r_1) \in F(X_1)$ and every $(H_2,\ell _2,r_2) \in F(X_2)$ such that graph $H_1+H_2$ is oriented, and $r_1=\ell _2$, we put $((V_1\cup V_2,E_1\cup E_2),\ell _1 ,r_2)$ into $F(X_1\times X_2)$.

After performing the rules given in Lemma 2 on every sub-expression of X, we can solve our problem by $\chi _o(G)=\min \{|V| \mid ((V,E),\ell ,r)\in F(X)\}$, which leads to the following result.

Theorem 3

Let G be an esp-digraph. Then, the oriented chromatic number of G can be computed in linear time.

4 Outlook

In our future work we want to analyze whether it is possible to compute oriented chromatic index and oriented chromatic number of orientations of series-parallel graphs efficiently in order to generalize Theorem 1 and Theorem 3.