Oriented graphs with no infinite paths

193 Views Asked by At

This question is based on a deleted question by user Ethan. I don't think it's what Ethan originally meant to ask, but I thought it was an interesting question.

Let $G = (V,E)$ be an infinite (simple and undirected) graph. An orientation of $G$ is a choice of direction $x\to y$ or $y\to x$ for each edge $\{x,y\}\in E$. Given an orientation of $G$, an infinite path is a sequence of vertices $(v_i)_{i\in \mathbb{N}}$ such that either $v_i\to v_{i+1}$ for all $i$ (this is a forwards path) or $v_{i+1}\to v_i$ for all $i$ (this is a backwards path). Note that any cycle in the orientation $a_1\to a_2\to \dots \to a_n\to a_1$ gives rise to infinite paths, both forwards and backwards.

Question: Which graphs admit an orientation with no infinite paths?

If $G$ contains an infinite clique $C$, then any orientation of $G$ has an infinite path. Proof: Enumerate a countably infinite subset $C'$ of $C$ by $C' = (v_i)_{i\in \mathbb{N}}$. For each pair $(v_i,v_j)$ with $i<j$, color this pair red if $v_i\to v_j$ and blue if $v_j\to v_i$. By Ramsey's theorem, there is an infinite monochromatic subset $H\subseteq C'$. If $H$ is monochromatic red, then its vertices (enumerated in increasing order) form an infinite forwards path. If $H$ is monochromatic blue, then its vertices (enumerated in increasing order) form an infinite backwards path.

On the other hand, if $G$ is $k$-colorable, then it admits an orientation in which every path has length at most $k$. This is the easy direction of the proof of the Gallai-Hasse-Roy-Vitaver theorem. The hard direction does not apply here, because having no infinite path is a much weaker assumption than the existence of a finite bound on the length of paths.

What happens if $G$ has no infinite clique, but is not $k$-colorable for any $k$?