Publication at Faculty of Mathematics and Physics |
2010
Abstract
We investigate bounds on the chromatic number of a grape G derived from the nonexistence of homomorphisms from some path (P) over right arrow into some orientation (G) over right arrow of G. The condition is often efficiently verifiable using boolean matrix multiplications.
However, the bound associated to a path (P) over right arrow depends on the relation between the "algebraic length" and "derived algebraic length" of (P) over right arrow. This suggests that paths yielding efficient bounds may be exponentially large with respect to G, and the corresponding heuristic may not be constructive.