Path homomorphisms, graph colourings and boolean matrices

We investigate bounds on the chromatic number of a graph G de-rived from the nonexistence of homomorphisms from some path ~P into some orientation ~G of G. The condition is often efficiently verifiable using boolean matrix multiplications. However, the bound associated to a path ~P depends on the relation between the “algebraic length” and “derived algebraic length ” of ~P. This suggests that paths yielding efficient bounds may be exponentially large with respect to G, and the corresponding heuristic may not be constructive. ∗Partially supported by the Project LN00A056 of the Czech Ministery of Education and by CRM Barcelona, Spain. †Supported by grants from NSERC and ARP 1