Let $(G_i)_{i\in I}$ denote a family of simple, undirected graphs (finite or infinite). Let $\prod_{i\in I}G_i$ denote their categorical product. Why do we have the inequality $$\chi(\prod_{i\in I}G_i) \leq \min\{\chi(G_i):i\in I\},$$ and not the other way round?

  • 1
    $\begingroup$ For all we currently know, there might be an inequality the other way round too (at least, for a finite family of finite graphs). That's exactly Hedetniemi's conjecture. Here's a categorical account: golem.ph.utexas.edu/category/2014/12/… $\endgroup$ – Tom Leinster Aug 20 '15 at 1:32

First, let me state that I don't believe this question is suitable for MO - but I'll give an answer anyway.

The categorical product (in any category) of a family of objects $(G_i)_{i\in I}$ is characterized by the fact that for every $j\in I$ there is a projection (a morphism that is canonical in some sense, see also the article you linked to) $$\text{pr}_j: \prod_{i\in I} G_i \to G_j.$$

Now, in the case of graphs, note that whenever there is a graph homomorphism $f: G\to H$ we have $\chi(G) \leq \chi(H)$. The reason is the following: a coloring of $H$ is a graph homomorphism $c: H \to K$ where $K$ is some complete graph, and so $c\circ f: G \to K$ is also a graph homomorphism, which implies directly that $\chi(G) \leq \chi(H)$.

In our particular case, the statement above implies that $\chi( \prod_{i\in I} G_i \leq \chi(G_j)$ for all $j\in I$, which is equivalent to $\chi( \prod_{i\in I} G_i \leq \min\{\chi(G_i):i\in I\}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.