Path homomorphisms, graph colorings, and boolean matrices

✍ Scribed by Jaroslav Nešetřil; Claude Tardif

• Publisher: John Wiley and Sons
• Year: 2010
• Tongue: English
• Weight: 124 KB
• Volume: 63
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20420

✦ Synopsis

Abstract

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