The chromatic number of an undirected graph can never be decreased by adding an edge. However, things are not that clear when we deal with coloring directed graphs - but first, the definition of this concept in the context of directed graphs.
If $X$ is a non-empty set, we say that $M\subseteq X$ is a majority if $|M| > |X\setminus M|$.
Let $G=(V,E)$ be a finite directed graph. For $v\in V$ we set $\text{In}(v)=\{x \in V: (x,v) \in E\}$.
Let $n$ be a positive integer. We say that a map $c:V(G) \to \{1,\ldots,n\}$ is a majority coloring if the following condition is satisfied:
For every $v\in V(G)$ with $\text{In}(v) \neq \emptyset$, if for some $k \in \{1,\ldots, n\}$ we have that $c^{-1}(\{k\}) \cap \text{In}(v)$ is a majority of $\text{In}(v)$, then $c(v) \neq k$.
We set the (directed) chromatic number $\chi_d(G)$ to be the least positive integer $j$ such that there is a majority coloring $c:V(G) \to \{1,\ldots,j\}$.
Is there a directed graph $G$ such that adding an edge decreases the directed chromatic number?
