The Parameterized Complexity of Coloring Mixed Graphs

In order to better explore the parameterized complexity of MixedColoring, we first introduce and analyze the generalizations of neighborhood diversity and cliquewidth to mixed graphs, which we call mixed neighborhood diversity ($\mathrm{𝗆𝗇𝖽}$) and mixed cliquewidth ($\mathrm{𝗆𝖼𝗐}$), respectively. Since in MixedColoring we can assume that the input graph does not contain directed cycles, we only analyze these parameters for mixed graphs without directed cycles. We explore their relationships with existing parameters defined on the underlying undirected graph, such as vertex cover ($\mathrm{𝗏𝖼}$), treedepth ($\mathrm{𝗍𝖽}$), pathwidth ($\mathrm{𝗉𝗐}$), feedback vertex set ($\mathrm{𝖿𝗏𝗌}$), treewidth ($\mathrm{𝗍𝗐}$), as well as neighborhood diversity ($\mathrm{𝗇𝖽}$) and cliquewidth ($\mathrm{𝖼𝗐}$); see the full version [26] for detailed definitions. Specifically, we show that $\mathrm{𝗆𝖼𝗐}$ strictly bounds $\mathrm{𝖼𝗐}$ (Proposition 1) and is strictly bounded by $\mathrm{𝗍𝗐}$ (Proposition 2). Similarly, we show that $\mathrm{𝗆𝗇𝖽}$ strictly bounds $\mathrm{𝗇𝖽}$ (Proposition 5) and is strictly bounded by $\mathrm{𝗏𝖼}$ (Proposition 6). Furthermore, we show that $\mathrm{𝗆𝗇𝖽}$ strictly bounds $\mathrm{𝗆𝖼𝗐}$ (Proposition 7), while $\mathrm{𝗆𝖼𝗐}$ and $\mathrm{𝗇𝖽}$ are incomparable (Proposition 8).

Since arcs enforce precedence constraints on the colors of the vertices, transitive arcs, i.e., arcs between vertices connected by a directed path along other arcs, do not influence the properness of colorings of mixed graphs. Adding all transitive arcs (and removing any edges parallel to transitive arcs) results in the transitive closure $G^{+}$ of a mixed graph $G$ (without directed cycles). We denote with ${\alpha }^{+}$ the transitive closure counterpart of the parameter $\alpha$, i.e., ${\alpha }^{+}(G)=\alpha (G^{+})$. We show that $\mathrm{𝗏𝖼}$, $\mathrm{𝗍𝖽}$, $\mathrm{𝗉𝗐}$, $\mathrm{𝖿𝗏𝗌}$, and $\mathrm{𝗍𝗐}$ are strictly bounded by their transitive closure counterparts (Proposition 9), while for $\mathrm{𝗆𝖼𝗐}$ and $\mathrm{𝗆𝗇𝖽}$ the situation is inverted, with $\mathrm{𝗆𝖼𝗐}$ and $\mathrm{𝗆𝗇𝖽}$ strictly bounding ${\mathrm{𝗆𝖼𝗐}}^{+}$ and ${\mathrm{𝗆𝗇𝖽}}^{+}$, respectively (Proposition 12). Meanwhile, $\mathrm{𝖼𝗐}$ and $\mathrm{𝗇𝖽}$ are incomparable to their transitive closure counterparts (Proposition 13). The resulting hierarchy of parameters is visualized in Figure 1.

Furthermore, we also consider bounds for the chromatic number ($\chi$) of mixed graphs, i.e., the minimum number of colors needed for a proper coloring. After providing some simple lower bounds, i.e., that the chromatic number of a mixed graph is lower-bounded by the chromatic number of the underlying undirected graph as well as by maxrank ($\mathrm{\Lambda }$), the length of the longest directed path, we generalize and tighten a bound by Gutowski et al. [18] on the chromatic number of mixed interval graphs (Theorem 15). Based on this, we show that the chromatic number of a mixed graph is bounded by ${\mathrm{𝗍𝗐}}^{+}$ as well as $\mathrm{𝗍𝖽}$ and $\mathrm{𝗏𝖼}$ (Corollary 17).

Using the newly established parameter relationships, we analyze the parameterized complexity of MixedColoring in Section 3. The results are summarized in Table 1 and visualized in Figure 1. We conclude with an outlook on open problems in Section 4.

For directed graphs, Neumann-Lara [28] introduced the dichromatic number and the corresponding coloring, where each color class induces an acyclic subgraph. This problem, known as DigraphColoring [21], also generalizes coloring undirected graphs, as each edge can be replaced by two opposite arcs. Therefore, DigraphColoring is $\mathrm{𝖭𝖯}$-hard. In contrast, MixedColoring is easy on directed graphs: if the graph is acyclic, greedily coloring vertices in topological order yields an optimal coloring. Otherwise, the graph cannot be properly colored. This difference arises due to the fact that DigraphColoring treats arcs very differently: in MixedColoring, there cannot be arcs between vertices of the same color, whereas in DigraphColoring there can be arcs between vertices of the same color, as long as these arcs do not form a directed cycle.

On directed acyclic graphs, MixedColoring, especially when considering the transitive closure, behaves somewhat similar to OrientedColoring [31], where, between each pair of color classes, all arcs must have the same orientation. However, contrary to MixedColoring, OrientedColoring does not forbid directed cycles.

For positive integer $k$, we use $[k]$ as shorthand for $\{1,\mathrm{\dots },k\}$. We say that a mixed graph $G$ is a partial orientation of its underlying undirected graph. The full versions of proofs marked with a (clickable) star ($\star$) can be found in the full version of this paper [26].

The first part follows directly from the definitions, as replacing all arc operations by edge operations in a mixed $\mathrm{\ell }$-expression constructing $G$ yields an $\mathrm{\ell }$-expression constructing the underlying undirected graph of $G$.

Let $\mathrm{AG}(G)$ be the subgraph of $G$ resulting from omitting all edges. It holds that $\mathrm{𝗆𝖼𝗐}(\mathrm{AG}(G))⩽\mathrm{𝗆𝖼𝗐}(G)$, as by omitting the edge operations in a mixed $\mathrm{\ell }$-expression constructing $G$ we obtain a mixed $\mathrm{\ell }$-expression for $\mathrm{AG}(G)$. Using this, we construct a family of mixed graphs ${(G_{\mathrm{\ell }})}_{\mathrm{\ell }⩾1}$ with $\mathrm{𝖼𝗐}(G_{\mathrm{\ell }})=2$ and $\mathrm{𝗆𝖼𝗐}(G_{\mathrm{\ell }})⩾\mathrm{\ell }+1$. We construct $G_{\mathrm{\ell }}$ by orienting an $(\mathrm{\ell }\times \mathrm{\ell })$-grid graph such that no directed cycles are created. As shown by Golumbic and Rotics [17], the cliquewidth of an $(\mathrm{\ell }\times \mathrm{\ell })$-grid graph is $\mathrm{\ell }+1$ and thus $\mathrm{𝗆𝖼𝗐}(G_{\mathrm{\ell }})⩾\mathrm{𝗆𝖼𝗐}(\mathrm{AG}(G_{\mathrm{\ell }}))⩾\mathrm{𝖼𝗐}(\mathrm{AG}(G_{\mathrm{\ell }}))=\mathrm{\ell }+1$. Furthermore, between any pair of vertices of $G_{\mathrm{\ell }}$ that are not connected by an arc, we add an edge. This results in the underlying undirected graph of $G_{\mathrm{\ell }}$ being a complete graph, which has cliquewidth $2$, and thus $\mathrm{𝖼𝗐}(G_{\mathrm{\ell }})=2$. $◀$

Courcelle and Olariu [6] showed that the cliquewidth of undirected as well as of directed graphs is bounded by treewidth. We can utilize their result for directed graphs to show that mixed cliquewidth (on mixed graphs without directed cycles) is also bounded by treewidth. To this end, we transform a mixed graph $G$ without directed cycles into its corresponding directed graph $D(G)$ by replacing each edge $\{u,v\}$ by two opposite arcs $(u,v)$ and $(v,u)$. Since mixed graphs without directed cycles cannot contain opposite arcs (as they would form a directed cycle of length two) this transformation is injective. We define the directed cliquewidth of a mixed graph $G$ without directed cycles, denoted $\mathrm{𝖽𝖼𝗐}(G)$, to be the (directed) cliquewidth of the corresponding directed graph $D(G)$. As we show now, mixed and directed cliquewidth are, while not equal, equivalent under the lens of parameterized complexity.

Converting a mixed $\mathrm{\ell }$-expression for $G$ into a directed $\mathrm{\ell }$-expression for $D(G)$ is straightforward, as we can replace each edge operation by two opposite arc operations. The inverse requires a careful manipulation of the $\mathrm{\ell }$-expression for $D(G)$, to ensure that we can replace pairs of opposite arc operations by edge operations.

The partial orientation $\tilde{G}$ of the star $K_{1,2}$, where the center vertex is connected to one leaf by an edge and to the other leaf by an outgoing arc, has $\mathrm{𝖽𝖼𝗐}(\tilde{G})=2$ and $\mathrm{𝗆𝖼𝗐}(\tilde{G})=3$. $◀$

In order to generalize neighborhood diversity to mixed graphs without directed cycles, we first need to define the different types of neighbors that occur in a mixed graph. Given a vertex $v$ of a mixed graph $G$, the outgoing neighbors of $v$, denoted by $N^{+}(v)$, are all vertices $u$ to which $v$ has an outgoing arc $(v,u)$. Analogously, the incoming neighbors of $v$, denoted by $N^{-}(v)$, are all vertices $u$ from which $v$ has an incoming arc $(u,v)$. The undirected neighbors of $v$, denoted by $N^{\mathrm{u}}(v)$, are all vertices $u$ which are connected to $v$ by an edge $\{u,v\}$. Thus, the neighborhood of a vertex $v$, denoted by $N(v)$, is the union of its incoming, outgoing, and undirected neighbors.

The parameter neighborhood diversity is defined for undirected graphs via an equivalence relation on the vertices, where two vertices $u,v$ are of the same type, denoted $u{\sim }_{\mathrm{𝗇𝖽}}v$, if they have the same neighbors, i.e., if $N(u)\setminus \{v\}=N(v)\setminus \{u\}$. We generalize this equivalence relation to mixed graphs by further distinguishing between incoming, outgoing, and undirected neighbors. Therefore, two vertices $u,v$ of a mixed graph $G$ are of the same (mixed) type, denoted $u{\sim }_{\mathrm{𝗆𝗇𝖽}}v$, if they have the same in-, out-, and undirected neighbors, i.e., if $N^{\mathrm{u}}(u)\setminus \{v\}=N^{\mathrm{u}}(v)\setminus \{u\}$, $N^{-}(u)=N^{-}(v)$, and $N^{+}(u)=N^{+}(v)$.

We call the partition of the vertices into equivalence classes under ${\sim }_{\mathrm{𝗆𝗇𝖽}}$ a mixed neighborhood partition. The mixed neighborhood diversity of a mixed graph $G$, denoted $\mathrm{𝗆𝗇𝖽}(G)$, is the number of equivalence classes under ${\sim }_{\mathrm{𝗆𝗇𝖽}}$. Note that this generalizes the definition of neighborhood diversity for undirected graphs. Furthermore, for mixed graphs without directed cycles, this is also a generalization of the definition of neighborhood diversity for directed graphs by Fernau et al. [11], as in directed graphs without directed cycles there are no opposite arcs. Note further that a mixed neighborhood partition can be obtained easily: it suffices to check, for each pair of vertices, whether they are of the same type.

As is the case for mixed cliquewidth and cliquewidth, the mixed neighborhood diversity can differ arbitrarily from the neighborhood diversity of the underlying undirected graph since each vertex in a directed path has to be of a different type, as we show now.

We know from Lemma 3 that there cannot be an arc between two vertices of the same type. Let $⟨v_0,v_1,\mathrm{\dots },v_{\mathrm{\ell }}⟩$ be a directed path of length $\mathrm{\ell }$ in $G$. Suppose that there are two vertices $v_i,v_j$ with that are of the same type. Since $v_{j-1}\in N^{-}(v_j)$, it follows that $v_{j-1}\in N^{-}(v_i)$. However, as $i⩽j-1$, it follows that there exists a directed path from $v_i$ to $v_{j-1}$ in $G$. Together with the arc $(v_{j-1},v_i)$, this yields a directed cycle, a contradiction to $G$ containing no directed cycles. $◀$

It follows directly from the definitions that two vertices of the same type w.r.t. $\mathrm{𝗆𝗇𝖽}$ must also be of the same type w.r.t. $\mathrm{𝗇𝖽}$. Indeed, if $u{\sim }_{\mathrm{𝗆𝗇𝖽}}v$, it holds that

(as there cannot be any arc between $u$ and $v$) and therefore $u{\sim }_{\mathrm{𝗇𝖽}}v$.

The inverse does not hold, as two vertices of the same type w.r.t. $\mathrm{𝗇𝖽}$ may differ in their in- or out-neighbors, as the following family ${(G_{\mathrm{\ell }})}_{\mathrm{\ell }⩾1}$ of graphs shows. The graph $G_{\mathrm{\ell }}$ is a partial orientation of the complete graph $K_{\mathrm{\ell }}$ obtained by orienting $\mathrm{\ell }-1$ edges such that the resulting mixed graph contains a directed Hamiltonian path. It holds that $\mathrm{𝗇𝖽}(G_{\mathrm{\ell }})=1$ but, due to Lemma 4, $\mathrm{𝗆𝗇𝖽}(G_{\mathrm{\ell }})⩾\mathrm{\ell }$. $◀$

Lampis [25] showed that neighborhood diversity is bounded by vertex cover, as the type of vertices not contained in the cover is determined uniquely by their neighbors (in the cover), resulting in a bound of $\mathrm{𝗏𝖼}+2^{\mathrm{𝗏𝖼}}$. Since mixed neighborhood diversity further distinguishes between in-, out-, and undirected neighbors, we obtain the following bound.

Let $C$ be a vertex cover of $G$ of size $\mathrm{𝗏𝖼}(G)$. Since each vertex in $V(G)\setminus C$ only contains neighbors in $C$, there are at most $4^{\mathrm{𝗏𝖼}(G)}$ different types of vertices in $V(G)\setminus C$, as each vertex in $C$ can be an in-, out-, or undirected neighbor, or not a neighbor at all. Further, there can be at most $\mathrm{𝗏𝖼}(G)$ different types of vertices in $C$, as $C$ contains $\mathrm{𝗏𝖼}(G)$ vertices. Thus, the total number of types is bounded by $\mathrm{𝗏𝖼}(G)+4^{\mathrm{𝗏𝖼}(G)}$. $◀$

If a parameter does not bound $\mathrm{𝗇𝖽}$ ($\mathrm{𝖼𝗐}$) on undirected graphs (or vice versa), it also does not bound $\mathrm{𝗆𝗇𝖽}$ ($\mathrm{𝗆𝖼𝗐}$) (or vice versa), as it holds that $\mathrm{𝗆𝗇𝖽}=\mathrm{𝗇𝖽}$ ($\mathrm{𝗆𝖼𝗐}=\mathrm{𝖼𝗐}$) on undirected graphs. Lampis [25] showed that $\mathrm{𝗇𝖽}$ bounds $\mathrm{𝖼𝗐}$ and that $\mathrm{𝗍𝗐}$ (and therefore $\mathrm{𝖼𝗐}$) does not bound $\mathrm{𝗇𝖽}$ ($\mathrm{𝗇𝖽}$ is even incomparable to $\mathrm{𝗍𝗐}$). It follows from this that $\mathrm{𝗆𝖼𝗐}$ does not bound $\mathrm{𝗆𝗇𝖽}$. Using a proof analogous to Lampis, we further obtain the following.

Regarding the relationship between $\mathrm{𝗆𝖼𝗐}$ and $\mathrm{𝗇𝖽}$, we already know that $\mathrm{𝗆𝖼𝗐}$ does not bound $\mathrm{𝗇𝖽}$ (due to $\mathrm{𝖼𝗐}$ not bounding $\mathrm{𝗇𝖽}$). However, while $\mathrm{𝗇𝖽}$ bounds $\mathrm{𝖼𝗐}$, it does not bound $\mathrm{𝗆𝖼𝗐}$. We show this by reusing the construction that we used to show that $\mathrm{𝖼𝗐}$ does not bound $\mathrm{𝗆𝖼𝗐}$ (Proposition 1), as detailed in the following.

Recall that an arc $(u,v)$ is transitive if there exists a directed path from $u$ to $v$ using other arcs. The transitive closure $G^{+}$ of a mixed graph $G$ is the mixed graph obtained by adding every transitive arc to $G$ (and removing any resulting parallel edges). As transitively closed graphs are a subset of mixed graphs, all bounds between parameters on mixed graphs also apply between their transitive closure counterparts. Further, if a parameter $\alpha$ does not bound a parameter $\beta$ on undirected graphs, then ${\alpha }^{+}$ does not bound ${\beta }^{+}$, as it holds that ${\alpha }^{+}=\alpha$ and ${\beta }^{+}=\beta$ on undirected graphs. Thus, it remains to analyze the relationship between the parameters and their transitive closure counterparts.

All parameters considered in this paper, except for neighborhood diversity and cliquewidth, have the well-known property that they bound their value on any subgraph. Since the underlying graph of the transitive closure of a mixed graph is a subgraph of the underlying graph of the original graph, it follows that these parameters are bounded by their transitive closure counterparts.

The second part can be shown using a family of oriented stars, where half of the edges are oriented towards the center vertex and the other half are oriented away from the center vertex. $◀$

However, for neighborhood diversity and cliquewidth (and their mixed variants), the situation is different. Contrary to the other parameters, these parameters are not bounded by their transitive closure counterparts, as shown in the following.

We first construct a family ${(G_{\mathrm{\ell }})}_{\mathrm{\ell }⩾1}$ of grid graphs where $2⩾{\mathrm{𝗆𝖼𝗐}}^{+}(G_{\mathrm{\ell }})⩾{\mathrm{𝖼𝗐}}^{+}(G_{\mathrm{\ell }})$ but $\mathrm{𝗆𝖼𝗐}(G_{\mathrm{\ell }})⩾\mathrm{𝖼𝗐}(G_{\mathrm{\ell }})=\mathrm{\ell }+1$. The graph $G_{\mathrm{\ell }}$ is a partial orientation of the $(\mathrm{\ell }\times \mathrm{\ell })$-grid graph where ${\mathrm{\ell }}^2-1$ edges are oriented such that $G_{\mathrm{\ell }}$ contains a directed Hamiltonian path, i.e., a directed path of length ${\mathrm{\ell }}^2-1$ containing all vertices. Golumbic and Rotics [17] showed that the cliquewidth of $(\mathrm{\ell }\times \mathrm{\ell })$-grid graphs is $\mathrm{\ell }+1$. Together with Proposition 1 we obtain that $\mathrm{𝗆𝖼𝗐}(G_{\mathrm{\ell }})⩾\mathrm{𝖼𝗐}(G_{\mathrm{\ell }})=\mathrm{\ell }+1$. As $G_{\mathrm{\ell }}$ contains a directed Hamiltonian path, it follows that $G_{\mathrm{\ell }}^{+}$ is the acylic tournament graph, the directed graph with exactly one arc between each pair of vertices (and without directed cycles). Using the following claim, we obtain that $2⩾{\mathrm{𝗆𝖼𝗐}}^{+}(G_{\mathrm{\ell }})⩾{\mathrm{𝖼𝗐}}^{+}(G_{\mathrm{\ell }})$.

For neighborhood diversity, we construct a separate family ${(G_{\mathrm{\ell }}^{\prime })}_{\mathrm{\ell }⩾1}$ based on tripartite graphs. The graph $G_{\mathrm{\ell }}^{\prime }$ consists of three independent sets $\{u_1,\mathrm{\dots },u_{\mathrm{\ell }}\}$, $\{v_1,\mathrm{\dots },v_{\mathrm{\ell }}\}$, and $\{w_1,\mathrm{\dots },w_{\mathrm{\ell }}\}$. We add arcs $(u_i,v_j)$ and $(v_i,w_j)$ for $i,j\in [\mathrm{\ell }]$, such that every $u$ has an outgoing arc to every $v$ and every $v$ has an outgoing arc to every $w$. To ensure that vertices of different sets are of different types, we further add three vertices $u^{\ast }$, $v^{\ast }$, and $w^{\ast }$. We then add edges $\{u^{\ast },u_i\}$, $\{v^{\ast },v_i\}$, and $\{w^{\ast },w_i\}$ for all $i\in [\mathrm{\ell }]$. Lastly, we add arcs $(u_i,w_i)$ for $i\in [\mathrm{\ell }]$. Thus, each vertex $u_i$ has a distinct type, as does every vertex $w_i$. Meanwhile, all vertices $v_i$ are of the same type. Further, the vertices $u^{\ast }$, $v^{\ast }$, and $w^{\ast }$ have distinct types. This results in $\mathrm{𝗆𝗇𝖽}(G_{\mathrm{\ell }}^{\prime })=\mathrm{𝗇𝖽}(G_{\mathrm{\ell }}^{\prime })=2\mathrm{\ell }+4$. However, in the transitive closure, each vertex $u_i$ has an outgoing arc to every vertex $w_j$ and therefore all $u_i$ are of the same type and all $w_i$ are of the same type, resulting in ${\mathrm{𝗆𝗇𝖽}}^{+}(G_{\mathrm{\ell }}^{\prime })={\mathrm{𝗇𝖽}}^{+}(G_{\mathrm{\ell }}^{\prime })=6$. $◀$

In fact, both mixed neighborhood diversity and mixed cliquewidth bound their transitive closure counterparts, as shown in the following.

For mixed neighborhood diversity, it holds that two vertices $u,v$ of the same type in $G$ are also of the same type in $G^{+}$, as the set of vertices to (from) which $u,v$ have outgoing (incoming) paths in $G$ are equivalent.

For mixed cliquewidth, we show that given a mixed $\mathrm{\ell }$-expression constructing $G$, we can obtain a $(4^{\mathrm{\ell }}\cdot \mathrm{\ell })$-expression constructing $G^{+}$. The idea is to keep track of the labels of vertices to which a given vertex $v$ has outgoing paths and the labels of vertices from which it has incoming paths. This can be achieved by using $4^{\mathrm{\ell }}$ additional labels for each original label. These additional labels then allow us to add the transitive arcs, resulting in the claimed bound. $◀$

The same does not hold for neighborhood diversity and cliquewidth, as these are in fact incomparable to their transitive closure counterparts, as the following shows.

We already know from Proposition 10 that these parameters are not bounded by their transitive closure counterparts. Thus, it remains to show that they do not bound their transitive closure counterparts. For this, we construct a family of graphs ${(G_{\mathrm{\ell }})}_{\mathrm{\ell }⩾2}$ such that $\mathrm{𝗇𝖽}(G_{\mathrm{\ell }})=\mathrm{𝖼𝗐}(G_{\mathrm{\ell }})=2$ while ${\mathrm{𝗇𝖽}}^{+}(G_{\mathrm{\ell }})⩾{\mathrm{𝖼𝗐}}^{+}(G_{\mathrm{\ell }})⩾\mathrm{\ell }+1$.

The graph $G_{\mathrm{\ell }}$ consists of ${\mathrm{\ell }}^2$ grid vertices and $2\mathrm{\ell }(\mathrm{\ell }-1)$ arc vertices and is constructed such that the grid vertices form an independent set in $G_{\mathrm{\ell }}$ but induce an $(\mathrm{\ell }\times \mathrm{\ell })$-grid in $G_{\mathrm{\ell }}^{+}$. This is achieved through the usage of the arc vertices, which connect two grid vertices adjacent in $G_{\mathrm{\ell }}^{+}$ with a directed path, thus ensuring that the transitive arc is present in $G_{\mathrm{\ell }}^{+}$. Further, each arc vertex is connected to all grid vertices via edges, except for those to which it is connected via an arc. This ensures that all arc vertices are of the same type and that all grid vertices are of the same type, resulting in $\mathrm{𝗇𝖽}(G_{\mathrm{\ell }})=\mathrm{𝖼𝗐}(G_{\mathrm{\ell }})=2$; see Figure 2 for an example of the construction for $\mathrm{\ell }=3$. As shown by Golumbic and Roctis [17], the cliquewidth of an $(\mathrm{\ell }\times \mathrm{\ell })$-grid is $\mathrm{\ell }+1$. Furthermore, it is easy to see that the cliquewidth of a graph bounds the cliquewidth of induced subgraphs. Thus, it follows that ${\mathrm{𝗇𝖽}}^{+}(G_{\mathrm{\ell }})⩾{\mathrm{𝖼𝗐}}^{+}(G_{\mathrm{\ell }})⩾\mathrm{\ell }+1$.

$◀$

Clearly, any proper coloring of a mixed graph is also a proper coloring of the underlying undirected graph and thus the chromatic number of the underlying undirected graph lower bounds the chromatic number of the mixed graph. Recall that the maxrank $(\mathrm{\Lambda })$ of a mixed graph is the length of the longest directed path in the graph. For a given vertex $v$, we define the inrank, denoted as ${\lambda }^{-}(v)$, as the length of the longest directed path ending in $v$. Furthermore, as vertices along a directed path must be colored increasingly, every vertex has a color that is at least its inrank. Thus, it holds that the chromatic number bounds the maxrank. We summarize these insights in the following proposition.

For undirected graphs, several (upper) bounds on the chromatic number are known, such as treewidth and maximum degree. However, these bounds do not generalize to mixed graphs, as a simple directed path of length $\mathrm{\ell }$ has treewidth $1$ and maximum degree $2$, but chromatic number $\mathrm{\ell }+1$. Gutowski et al. [18, Theorem 9 & Proposition 10] showed that for mixed interval graphs it holds that $\chi ⩽(\mathrm{\Lambda }+1)\cdot \omega$, where $\omega$ is the clique number, and that this bound is asymptotically tight. They achieved this by introducing the concept of layering, which is a partition of the vertex set into $\mathrm{\Lambda }+1$ layers $⟨L_0,\mathrm{\dots },L_{\mathrm{\Lambda }}⟩$ such that the layer $L_i$ contains all vertices of inrank $i$. In a layering, each arc is oriented towards the higher layer, as it must hold for every arc $(u,v)$ that . It follows that each subgraph $G[L_i]$ induced by a layer $L_i$ is an undirected graph. Thus, we can iteratively color each layer with disjoint color sets, resulting in a proper coloring of the entire graph as formalized in the following theorem.

Regarding the transitive closure, note that ${\mathrm{\Lambda }}^{+}=\mathrm{\Lambda }$ and ${\chi }^{+}=\chi$, as adding transitive arcs neither changes the length of the longest directed path nor the validity of a coloring. Thus, we obtain the following bounds on maxrank.

As the chromatic number of a subgraph is a lower bound for the chromatic number of the entire graph, it follows from Theorem 15 and Proposition 16 that any parameter that bounds the chromatic number of undirected graphs as well as the maxrank also bounds the chromatic number of mixed graphs.

The resulting hierarchy is visualized in Figure 1.

Given a set of strings $𝒮$ over the binary alphabet $\{0,1\}$ and a positive integer $k$, the problem ShortestSuperstring asks whether there is a string of length at most $k$ that is a superstring of each string in $𝒮$. ShortestSuperstring is $\mathrm{𝖭𝖯}$-hard [29].

We reduce from ShortestSuperstring by constructing a mixed graph $G$ such that a proper $k$-coloring of $G$ corresponds to a length-$k$ superstring of $𝒮$. We achieve this by creating a directed path $P_S$ for each string $S$ in $𝒮$ such that the vertices of the path correspond to the characters of the string; we add edges such that vertices corresponding to different characters cannot receive the same color. See Figure 3(a) for an example. Thus, the color of a vertex corresponds to the position of the corresponding character in the superstring, and the directions of the paths enforce that the characters of each string appear in the correct order.

To ensure a constant maxrank, we then split each directed path $P_S$ at every vertex into two vertices, with one vertex obtaining the incoming and the other the outgoing arc. We then connect each new pair of vertices to a distinct $(k-1)$-clique, thus enforcing that the two vertices receive the same color in any proper $k$-coloring; see Figure 3(b). Therefore, regarding proper $k$-colorings, they can be treated as a single vertex, while the maxrank of the resulting graph is $1$, due to all directed paths having been split. Furthermore, the resulting graph has a mixed cliquewidth of at most $6$. $◀$

We reduce from the following problem, which is $\mathrm{𝖭𝖯}$-hard [16, SS9].

Given an instance $(T_1,T_2,\prec ,D)$ of PrecedenceConstrainedScheduling, we create a $4D$-MixedColoring instance $G$ such that each block of four consecutive colors corresponds to one time unit on the machines.

First, we create a directed path $P$ consisting of $4D$ vertices $⟨p_1,\mathrm{\dots },p_{4D}⟩$, which we will use to ensure that each task is scheduled on its assigned machine. Note that in any proper $4D$-coloring, the path $P$ has the same unique coloring, with each vertex $p_i$ receiving the color $i$. For each task $t\in T_1\cup T_2$, we create two task vertices, the start vertex $v_t^{-}$ and the end vertex $v_t^{+}$, connected via the arc $(v_t^{-},v_t^{+})$. We denote with ${[i]}_k$ the set of integers that are congruent to $i$ modulo $k$. For each start vertex $v_t^{-}$ of a task $t$ in $T_1$, we add an edge to each vertex $p_i$ of the path $P$ with $i\notin {[1]}_4$. As a result, $v_t^{-}$ receives a color in ${[1]}_4$ in every proper $4D$-coloring of $G$. Analogously, we add edges between each end vertex $v_t^{+}$ of a task $t$ in $T_1$ and each vertex $p_i$ of the path $P$ with $i\notin {[3]}_4$ to ensure that $v_t^{+}$ receives a color in ${[3]}_4$. For tasks in $T_2$, we similarly add edges to ensure that the start vertices receive colors in ${[2]}_4$ and the end vertices receive colors in ${[4]}_4$. The precedence constraints are enforced by adding arcs between the corresponding tasks, i.e., for each $t,t^{\prime }\in T_1\cup T_2$ with $t\prec t^{\prime }$ we add the arc $(v_t^{+},v_{t^{\prime }}^{-})$. Lastly, it remains to ensure that no two tasks are scheduled at the same time on the same machine. We achieve this by adding (undirected) edges such that the underlying undirected graph induced by the task vertices forms a clique. An example of the resulting graph is shown in Figure 4.

As these claims show, the resulting MixedColoring instance is equivalent to the original PrecedenceConstrainedScheduling instance, with the neighborhood diversity of the transitive closure being $8$. Thus, MixedColoring is paraNP-hard w.r.t. neighborhood diversity, even when considering the neighborhood diversity of the transitive closure. $◀$

The picture changes if we parameterize by mixed neighborhood diversity.

Let $G$ be a mixed graph. We can assume w.l.o.g. that each type of $G$ induces a clique, as all vertices of a type inducing an independent set can be merged into a single vertex. This is due to the fact that they have the same neighborhoods and therefore can be assigned the same color. Let $𝒮=\{C_1,\mathrm{\dots },C_{\mathrm{𝗆𝗇𝖽}}\}$ be the set of types of $G$, where each $C_i$ is a clique in $G$. In the following, we write $\{C_i,C_j\}\in E(G)$ and $(C_i,C_j)\in A(G)$ to express that there is an undirected edge or a directed arc, respectively, between the types $C_i$ and $C_j$ in $G$. For a coloring $c$ of $G$ and a set $U\subseteq V(G)$, let $c(U)=\{c(u):u\in U\}$. If $c$ is proper, then, for every $(C_i,C_j)\in A(G)$, all colors in $c(C_i)$ are smaller than all colors in $c(C_j)$. We define a type-endpoint preorder $p$ as a function that assigns, to each type $C$, two integers $p^{-}(C),p^{+}(C)\in [\mathrm{\ell }]$ (with and $\mathrm{\ell }⩽2\mathrm{𝗆𝗇𝖽}$), which we call the type endpoints of $C$. We say that a coloring $c$ corresponds to a type-endpoint preorder $p$ if there is a sequence $⟨c_1,\mathrm{\dots },c_{\mathrm{\ell }}⟩$ of $\mathrm{\ell }$ ascending (not necessarily consecutive) colors such that, for each type $C$, the set $c(C)$ is contained in the halfopen interval $[c_{p^{-}(C)},c_{p^{+}(C)})$. We say that a (type-endpoint) preorder $p$ is proper if, for each arc $(C_i,C_j)\in A(G)$, it holds that $p^{+}(C_i)⩽p^{-}(C_j)$. An example of a proper preorder and a corresponding coloring is shown in Figure 5.

In total, there are $2\mathrm{𝗆𝗇𝖽}$ type endpoints and thus at most $(2\mathrm{𝗆𝗇𝖽})!$ orders of these endpoints. Since type endpoints can be equal, there are at most $(2\mathrm{𝗆𝗇𝖽})!\cdot 2^{2\mathrm{𝗆𝗇𝖽}}\in 2^{𝒪(\mathrm{𝗆𝗇𝖽}\log \mathrm{𝗆𝗇𝖽})}$ (proper) preorders. Therefore, we can enumerate all proper preorders in $\mathrm{𝖥𝖯𝖳}$-time w.r.t. mixed neighborhood diversity. We can thus check whether $G$ is $k$-colorable by checking, for each proper preorder $p$, whether there exists a proper $k$-coloring of $G$ that corresponds to $p$. Since we know that such a coloring does not violate any arcs, it suffices to check whether it does not violate any edges. This problem has similarities to Coloring, differing in that we additionally require the colors within each type to adhere to the given preorder. For Coloring, Ganian [15] provided an $\mathrm{𝖥𝖯𝖳}$-algorithm w.r.t. neighborhood diversity based on an ILP. In the following, we adapt his ILP to additionally respect a given proper preorder $p$.

Since we only need to decide whether there exists a $k$-coloring $c$ of $G$ that corresponds to the given proper preorder $p$, we do not need an objective function. For an overview of the ILP, see the full version [26]. We have two kinds of variables. First, for every $i\in [\mathrm{\ell }]$, we introduce an integer variable $c_i\in [k]$ to obtain a sequence $⟨c_1,\mathrm{\dots },c_{\mathrm{\ell }}⟩$ of colors. We enforce that these colors form an ascending sequence (by adding, for each $i\in [\mathrm{\ell }-1]$, the constraint $c_i+1⩽c_{i+1}$). Second, for each $i\in [\mathrm{\ell }-1]$ and each subset ${𝒮}^{\prime }\subseteq 𝒮$, we introduce an integer variable $x_{{𝒮}^{\prime },i}\in \{0,\mathrm{\dots },k\}$, which represents the number of colors in the interval $[c_i,c_{i+1})$ that are shared exclusively by the types in ${𝒮}^{\prime }$. Formally, we want that $x_{{𝒮}^{\prime },i}=|\{d\in [c_i,c_{i+1})\mid (\forall C\in {𝒮}^{\prime }:d\in c(C))\wedge (\forall C\in 𝒮\setminus {𝒮}^{\prime }:d\notin c(C))\}|$, where $c(C)$ is the set of colors assigned to the vertices of type $C$ by the coloring $c$; see Figure 5 for an example. For each $i\in [\mathrm{\ell }-1]$, we need to ensure that the ILP does not assign too many colors in the interval $[c_i,c_{i+1})$. We achieve this by adding the constraint ${\sum }_{{𝒮}^{\prime }\subseteq 𝒮}{x}_{{𝒮}^{\prime },i}⩽c_{i+1}-c_i$. Moreover, we want the coloring to correspond to the given preorder $p$. To achieve this, for each type $C$, we first ensure that no color is assigned to $C$ (by adding the constraint ${\sum }_{i=1}^{p^{-}(C)-1}{\sum }_{{𝒮}^{\prime }\subseteq 𝒮:C\in {𝒮}^{\prime }}{x}_{{𝒮}^{\prime },i}=0$). Second, we ensure that enough colors are assigned to $C$ in the interval formed by its two type endpoints (by adding the constraint ${\sum }_{i=p^{-}(C)}^{p^{+}(C)-1}{\sum }_{{𝒮}^{\prime }\subseteq 𝒮:C\in {𝒮}^{\prime }}{x}_{{𝒮}^{\prime },i}=|C|$). Third, we ensure that no color $d⩾c_{p^{+}(C)}$ is assigned to $C$ (by adding the constraint ${\sum }_{i=p^{+}(C)}^{\mathrm{\ell }-1}{\sum }_{{𝒮}^{\prime }\subseteq 𝒮:C\in {𝒮}^{\prime }}{x}_{{𝒮}^{\prime },i}=0$). It remains to ensure that no two types connected by an edge share a color. To this end, for each $i\in [\mathrm{\ell }-1]$ and each set ${𝒮}^{\prime }\subseteq 𝒮$ that contains types $C$ and $C^{\prime }$ with $\{C,C^{\prime }\}\in E(G)$, we add the constraint $x_{{𝒮}^{\prime },i}=0$.

It is well known [12, Theorem 9.19] that an ILP can be solved in $\mathrm{𝖥𝖯𝖳}$-time w.r.t. the number of variables. Hence, we can solve the ILP in $\mathrm{𝖥𝖯𝖳}$-time w.r.t. mixed neighborhood diversity as it uses $𝒪(2^{\mathrm{𝗆𝗇𝖽}}\cdot \mathrm{𝗆𝗇𝖽})$ variables. Therefore, by enumerating all proper preorders and checking for each preorder whether a corresponding proper $k$-coloring exists, we can decide in $\mathrm{𝖥𝖯𝖳}$-time w.r.t. mixed neighborhood diversity whether $G$ is $k$-colorable. $◀$

Furthermore, while MixedColoring is paraNP-hard w.r.t. neighborhood diversity, it becomes $\mathrm{𝖥𝖯𝖳}$ if we use the chromatic number as an additional parameter.

It was shown by Christofides [3] that there exists an optimal coloring of an (undirected) graph where one color class forms a maximal independent set. However, this property does not hold for mixed graphs; see Figure 6. Fortunately, we can strengthen the property by only considering maximal independent sets of vertices with inrank $0$, i.e., vertices without incoming arcs, resulting in the following formula for the chromatic number.

Furthermore, we can bound the number of maximal independent sets in the subgraph induced by vertices of inrank $0$ by neighborhood diversity and clique number, as the following shows.

We implement the recursive formula for the chromatic number as a branching algorithm for MixedColoring as follows: Given a mixed graph $G$ and a number of colors $k$, we branch on all maximal independent sets $I$ in the subgraph induced by the vertices of inrank $0$ and recursively check whether $G-I$ is $(k-1)$-colorable until we either reach the empty graph or run out of colors. Thus, the recursion depth is bounded by $k$. As in each step we branch into at most ${(\omega (G)+1)}^{\mathrm{𝗇𝖽}(G)}$ subproblems, this results in an overall runtime of ${𝒪}^{\ast }({(\omega (G)+1)}^{\mathrm{𝗇𝖽}(G)\cdot k})$, which is $\mathrm{𝖥𝖯𝖳}$ w.r.t. neighborhood diversity plus chromatic number, as $\chi (G)⩾\omega (G)$. $◀$