Randomized graph products, chromatic numbers, and the Lovász ϑ-function

Chromatic numbers of products of graphs:

Chromatic numbers of products of graphs: The directed and undirected versions of the Poljak-Rödl function

✍ Claude Tardif; David Wehlau 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 61 KB

## Abstract Let __f__(__n__) = min{χ(__G__ × __H__) : __G__ and __H__ are __n__‐chromatic digraphs} and __g__(__n__) = min{χ(__G__ × __H__) : __G__ and __H__ are __n__‐chromatic graphs}. We prove that __f__ is bounded if and only if __g__ is bounded. © 2005 Wiley Periodicals, Inc. J Graph Theory