Abstract:We provide the list of all paths with at most $16$ arcs with the property that if a graph $G$ admits an orientation $\vec {G}$ such that one of the paths in our list admits no homomorphism to $\vec {G}$, then $G$ is $3$-colourable.
Keywords: graph colourings, paths, Hasse-Gallai-Roy Theorem
AMS Subject Classification: 05C15