3
$\begingroup$

Prove that a graph is $k$-colourable iff its edges can be oriented in such a way that the resulting directed graph does not contain a path of length $k$.

It seems to me that the '$\Leftarrow$' implication might be slightly easier to show if we were to consider directed acyclic graphs (then we could assign subsequent colors to vertices as we traverse along a path and do some rearranging when we visit an already coloured vertex)... But I am stuck at finding a valid argument that justifies the implication in either direction, not to mention I am actually interested in a stronger statement.

$\endgroup$
2
$\begingroup$

For the forward direction, let the colors be $\{1,2,\ldots, k\}$ and orient each edge to go from the higher color to the lower one.

$\endgroup$
1
$\begingroup$

Perhaps you could use the Gallai-Hasse-Roy-Vitaver Theorem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.