Orientations and $3$-colourings of graphs
Vincent Chouinard-Prévost, Alexandre Côté, Claude Tardif · Czech digital mathematics library · 2004
summary: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.