Vertex Colourings for Directed graphs My question is this;
Show that $\chi (G) \leq k$ if and only if the edges of G can be oriented in such a way that no directed path contains more than k vertices. 
(Hint: To prove the backward direction, delete a set of edges of minimum size that destroys all the directed cycles. Let H be the directed subgraph of G obtained in this way. Colour a vertex x with $i \leq k$ if the longest directed path in H which starts in x has I vertices. Show that this has a proper colouring of G.) 
I have no idea of where to start!
Kindest regards
 A: Suppose that the graph can be colored with colors $1,2\dots m$ with $m\leq k$. Direct the graph so that a every edge goes from the smaller color to the larger color. Clearly no directed path with more than $m$ vertices can exist, as the colors are increasing along each path. So the forward implication is trivial.
The backwards implication is the hard one, the idea has a flavor similar to the proof of the Erdös-Szekeres theorem. Suppose that the graph can be directed in such a way that no path contains more than $k$ vertices, we are going to color it using colors $1,2,\dots, k$. Let $H$ be a graph obtained from $G$ by removing an edge set of minimum size.
We now color vertex $v$ with the length of the longest path in $H$ ending with $v$ (which is of course at most $k$). Clearly no two vertices of the same color can be joined by an edge in $H$, Suppose that an edge in $H$ from $u$ to $v$ exists, let $x_1,x_2,\dots,u$ be the longest path in $H$ ending in $u$, then either $x_1,x_2,\dots ,u,v$ is a longer path in $H$ ending in $v$ or it contains repeated vertices and thus a directed cycle.
So now suppose that there is an edge in $G\setminus H$ going from $u$ to $v$ such that $u$ and $v$ have the same color, there must be a directed cycle that uses $uv$ and no other vertex from $G\setminus H$ (because the set of removed edges is of minimum size). Let $u,v,x_1,\dots ,x_nu$ be the cycle, Let $y_1,y_2,\dots,y_n,v$ be the longest path in $H$ ending in $v$, then either $y_1,y_2,\dots,y_n,v,x_1,\dots,u$ is a longer path in $H$ ending in $v$ or it contains repeated vertices and thus a directed cycle.
