-1
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 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
    Commented Aug 20, 2015 at 1:32

1 Answer 1

Reset to default
2
$\begingroup$

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\}$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .