2
$\begingroup$

Are there graphs $G, H$ such that $\chi(G) = \chi(H) = \aleph_0$, but $\chi(G\times H) < \aleph_0$?

$\endgroup$

2 Answers 2

8
$\begingroup$

The existence of such a pair of graphs would contradict Hedetniemi's conjecture for finite graphs.

Suppose $\chi(G \times H) = k < \aleph_0$ then $\chi(G_0 \times H_0) \leq k$ for all finite induced subgraphs $G_0$ and $H_0$ of $G$ and $H$, respectively. If $\chi(G) > k$ then this is witnessed by a finite induced subgraph $G_0$ of $G$. Assuming Hedetniemi's conjecture, we must then have $\min(\chi(G_0),\chi(H_0)) = \chi(G_0 \times H_0) \leq k$ for every finite induced subgraph $H_0$ of $H$. Since $\chi(G_0) > k$, we must have $\chi(H_0) \leq k$. But then $H$ must be $k$-colorable since every finite induced subgraph of $H$ is $k$-colorable.

In other words, the above shows that if Hedetniemi's conjecture holds for all finite graphs, then it also holds for infinite graphs when at least one of the factors is finitely or countably colorable.

In fact, one can say more about the exact relationship with Hedetniemi's conjecture. Consider the function $$h(n) = \min\{\chi(G \times H) : \chi(G), \chi(H) \geq n\}.$$ On the one hand, Hedetniemi's conjecture is equivalent to $h(n) = n$ for all $n$. On the other hand, the existence of two graphs $G, H$ with $\chi(G), \chi(H) \geq \aleph_0$ and $\chi(G \times H) < \aleph_0$ is equivalent to the statement that $h$ is bounded.

$\endgroup$
1
  • 2
    $\begingroup$ The people I know who have devoted serious attention to the finite version of Hedetniemi's conjecture seem to believe it is likely false. $\endgroup$ Aug 21, 2015 at 5:18
7
$\begingroup$

No; this is a theorem of Hajnal. Suppose $G$ is a graph such that $\chi(G)$ is infinite, and say that a set of vertices of $G$ is chromatically cofinite if the induced subgraph on the complement is finitely colorable. The collection of chromatically cofinite sets is a filter; extend it to an ultrafilter $U$. Note that every $A\in U$ (as an induced subgraph of $G$) has infinite chromatic number, and in particular has many edges.

Now suppose you have a proper $n$-coloring $\alpha:G\times H\to \{1,\dots,n\}$ for some graph $H$. For each $g\in G$, this determines a function $\alpha_g: H\to\{1,\dots,n\}$ given by $\alpha_g(h)=\alpha(g,h)$; let $\alpha_U:H\to\{1,\dots n\}$ be the limit of the $\alpha_g$ with respect to the ultrafilter $U$ (i.e. $\alpha_U(h)=i$ iff $\alpha_g(h)=i$ for a set of $g$ that is in $U$). Then $\alpha_U$ is a proper $n$-coloring of $H$. Indeed, if $h,h'\in H$ are adjacent and $\alpha_U(h)=\alpha_U(h')=i$, then the set $A=\{g:\alpha_g(h)=\alpha_g(h')=i\}$ is in $U$. We can thus find $g,g'\in A$ which are adjacent, and then $(g,h)$ is adjacent to $(g',h')$ in $G\times H$. But $\alpha(g,h)=\alpha(g',h')=i$ and $\alpha$ is a proper coloring of $G\times H$, so this is a contradiction.

$\endgroup$
1
  • $\begingroup$ Excellent! What a wonderful argument! As a consequence, the function $h$ at the end of my answer must be unbounded. $\endgroup$ Aug 20, 2015 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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