Bounds on the chromatic number of a directed graph given bounds on out degree. We defined a coloring of a directed graph to be equivalent to the coloring of the undirected graph with the same edges.
The problem asks us to show if $\deg^+(v)\leq k$ for all $v \in V(G)$, then $\chi(G) \leq 2k+1$.  I have attempted to apply some sort of coloring analogous to the greedy algorithm for undirected graphs but have not had luck so far.  Are there any hints to point me in the right direction?
 A: I agree that you should imitate the proof that $\chi(G)\leq \Delta(G)+1$ for an undirected graph $G$. In your case, instead of deleting a vertex of degree $\Delta(G)$ in order to apply the inductive hypothesis, delete a vertex of in-degree at most $k$. Of course, you need to show that such a vertex always exists (Hint: consider the average in-degree.)
A: In view of the Erdős-De Bruijn theorem it will suffice to consider the case of a finite graph $G$.
The proof is by induction on $n$, the order (number of vertices) of the digraph. The case $n=1$ is trivial. Assume that $n\gt1$ and the theorem holds for digraphs of order $n-1$. Since the maximum outdegree is $\le k$, it follows that the number of edges is $\le nk$, whence the sum of the (undirected) degrees is $\le2nk$, the average degree is $\le2k$, and so the minimum degree is $\le2k$. Choose a vertex $v\in V(G)$ with $d(v)\le2k$. By the induction hypothesis, the graph $G-v$ has a proper vertex coloring with $2k+1$ colors; the degree condition on $v$ ensures that the coloring can be extended to $G$.
A: This proof I've given below is a bit more wordy and a bit less "mathy," but extracting the formalism out of it shouldn't be too hard. I'm curious if there's a neat non-inductive proof of this, but here's what I have:
For $k = 0$, the graph is an independent graph, so it can be $1$-colored trivially. 
Assume for $k = n$, $\chi(G) \leq 2n+1$, where for all $x \in V$, $\deg(x)^{+}\leq n$. 
For $k = n+1$, we take out an "out" edge (provided one exists) for all $x \in V$. Denote this graph $G'$. This leaves a graph where $\deg(x)^{+}\leq n$, for all $x \in V$. By hypothesis, $\chi(G') \leq 2n+1$. Now, we turn our attention to the paths we cut out. I claim that what is left forms a cycle, a tree, or some number of cycles with some number of trees attached. This is clear because, from any vertex, we can follow the edge we added to another vertex and keep following edges until we either reach an edge with no out vertex or we hit a vertex we've already been at. The chromatic number of any of these is less than or equal to $3$, so if we treat the already colored portion of the graph as one color in a sense, we can add two colors to make sure we get the rest. Thus, we have that $\chi(G) \leq 2n+3 = 2(n+1)+1$. Thus we have the result.
