Path Homomorphisms, Graph Colorings, and Boolean Matrices

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F10%3A10081055" target="_blank" >RIV/00216208:11320/10:10081055 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Path Homomorphisms, Graph Colorings, and Boolean Matrices
Original language description
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.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2010
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)