Path homomorphisms,graph colorings,and boolean matrices

We investigate bounds on the chromatic number of a graph G derived from the nonexistence of homomorphisms from some path begin{eqnarray*}vec{P}end{eqnarray*} into some orientation begin{eqnarray*}vec{G}end{eqnarray*} of G. The condition is often efficiently verifiable using boolean matrix multiplications. However, the bound associated to a path begin{eqnarray*}vec{P}end{eqnarray*} depends on the relation between the “algebraic length” and “derived algebraic length” of begin{eqnarray*}vec{P}end{eqnarray*}. 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