Prove $\chi(G) \le \ell + 1$, where $\ell$ is the length of a longest path in $G$.

122 Views Asked by At

Is it possible use The Gallai-Roy-Vitaver Theorem to prove the following result?

For every orientation $D$ of a graph $G$, $\chi(G) \le 1 + l(D)$.

Is it correct to say that $l(G) \ge l(D)$, so by Gallai-Roy Theorem $\chi(G) \le 1 + l(G)$?