Chromatic number $χ(G) > k$ implies existence of path of length $k$ Show that if $G$ is a loopless graph, $k≥1$ is an integer and $χ(G) > k$ then $G$ has a path with $k$ edges.
So, we can assume WLOG that $G$ is connected. we're looking for a path $P$ where $|V(P)| = k+1 $ and $|E(P)| = k.$  I'm stuck with this question. I know that $χ(G) < d(G) + 1$   where $d(G)$ is the maximum vertex degree of $G$. If $χ(G)= k+1$ , then there must be at least $k+1$ vertices of degree $> k$. I'm not sure how to take it from there, or if I'm even in the right direction. Can anyone please help??
 A: Let $\ell$ denote the length of the longest path in $G$ with chromatic number $\chi > k$. The minimal degree of $G$ satisfies $\delta \ge \chi - 1 \ge k$ and the longest path satisfies $\ell \ge \delta$. Therefore $\ell \ge k$.
Edit: I made a small mistake in the above, but the idea is the same. Let $G$ be a $\chi$-chromatic graph where $
\chi > k$. Then $G$ contains a $\chi$-critical subgraph $H\subseteq G$. For the $\chi$-critical graph $H$, we have $\delta_H \ge \chi - 1$ where $\delta_H$ is the smallest vertex degree of $H$. 
We know that a graph with least degree $\delta$ necessarily has a path of length at least $\delta$ so it follows that the longest path of $H$ is of length at least
$$\delta_H \ge \chi - 1 \ge k$$
So $H$ contains a path of length at least $k$ and therefore $G$ also contains the same path.
A: We know that any chromatic coloring can be made into Grundy coloring (Grundy k-coloring is a proper k-coloring in which for any i=2,3...,k each vertex receiving color i has a neighbor in a vertex which receives color j, for all j
A: Give $G$ an acyclic orientation. For each vertex $v$ let $f(v)$ be the length of the longest directed path from $v.$ Clearly, if $uv$ is a directed edge, then $f(u)\ge1+f(v)\gt f(v).$ Therefore $f$ is a proper coloring. Since $\chi(G)\gt k,$ and the values of $f$ are nonnegative integers, there must be a vertex $v$ with $f(v)\ge k;$ i.e., there is a directed path from $v$ of length at least $k.$
