We investigate bounds on the chromatic number of a graph G derived from the nonexistence of homomorphisms from some path \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray*}\vec{P}\end{eqnarray*}\end{document} into some orientation \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray*}\vec{G}\end{eqnarray*}\end{document} of G. The condition is often efficiently verifiable using boolean matrix multiplications. However, the bound associated to a path \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray*}\vec{P}\end{eqnarray*}\end{document} depends on the relation between the “algebraic length” and “derived algebraic length” of \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray*}\vec{P}\end{eqnarray*}\end{document}. This suggests that paths yielding efficient bounds may be exponentially large with respect to G, and the corresponding heuristic may not be constructive. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 198–209, 2010