Vincent Chouinard-Pr\'evost, Alexandre C\^ot\'e, Claude Tardif
Orientations and $3$-colourings of graphs

Comment.Math.Univ.Carolinae 45,3 (2004) 549-553.

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

PDF