Arched coloring of graph: $A(D) \ge \log \chi(D)$ Let $D$ be a directed graph. Arched coloring of $D$ is any coloring of edges such that $$ \forall_{a,b} (a,b) \mbox{ and } (b,c) $$
have different colors for any $(a,b), (b,c) \in E(D) $. A(D) is the smallest number of colors on which we can arche color $D$. Proof that
$$ A(D) \ge \log \chi(D) $$
Idea
I have drawn $K_4$ and had idea that I can color each vertex with color:
$$0,1,2,...,\chi(G)-1$$
and then color $(a,b)$ on $color(a)+color(b) \mod \lceil\log\chi(G)\rceil $. And for $K_n$ it seems to work. But I have just checked that way on very small example like path $P_3$.  $\chi(P_3) = 2$ and colors will be $0,1,0$ so colors of path will be just $1$ and $1$ so it is wrong.
 A: If you want to show that $A(D) \ge \log \chi(D)$, then the natural strategy is to use an arc-coloring of $D$ with $A(D)$ colors to define a vertex-coloring of $D$ with $2^{A(D)}$ colors (getting an upper bound on $\chi(D)$). Even if you succeeded in going the other way, using a vertex coloring to define an arc-coloring, you would get the reverse inequality.
One way to rephrase the condition for a proper arc-coloring is that for every vertex $v$ and for every color $c$, there cannot be both an edge into $v$ and en edge out of $v$ given the color $c$.
Given this observation (and an arc-coloring of $D$ with $A(D)$ colors), a natural labeling of the vertices of $D$ with $2^{A(D)}$ values is to give each vertex $v$ a label $f(v) \in \{-1,1\}^{A(D)}$ where:


*

*$f_i(v) = -1$ if all edges of color $i$ incident to $v$ are oriented into $v$.

*$f_i(v) = +1$ if all edges of color $i$ incident to $v$ are oriented out of $v$.

*$f_i(v)$ is arbitrary if there are no edges of color $i$ incident to $v$.


Now we just check that this is a proper coloring. If $(v,w)$ is any edge, let $i$ be its color. Then $f_i(v) = +1$, because the edge $(v,w)$ has color $i$ and is oriented out of $v$, and $f_i(w) = -1$, because the edge $(v,w)$ has color $i$ and is oriented into $w$. Therefore $f(v) \ne f(w)$.
