# Induced subgraphs of any given smaller chromatic number

Let $$G = (V,E)$$ be a simple, undirected graph with $$\chi(G)$$ infinite. Given a cardinal $$\kappa$$ with $$0 < \kappa < \chi(G)$$, is there an induced subgraph $$S$$ of $$G$$ with $$\chi(S) = \kappa$$?

What I tried: Let $${\cal S}$$ be the collection of all subgraphs of $$G$$ colorable with $$\kappa$$ colors. I hoped to find a maximal element $$M$$ in $${\cal S}$$ using Zorn's Lemma, establishing $$\chi(M) = \kappa$$. But this approach does not work.

• This might be rather naïve, but is there a graph whose chromatic number $\chi$ is uncountably infinite but which does not contain a clique of size $\chi$? Jul 30, 2021 at 14:25
• In my first comment, one should probably assume that $\chi$ is not the supremum of a set of strictly smaller cardinals (I do not know whether there is a name for this). Jul 30, 2021 at 14:41
• Thanks @M.Winter for your question and comments. There are triangle-free graphs (no clique has size > 2) having arbitrarily large chromatic number. Jul 30, 2021 at 15:46
• @M.Winter The name for that condition is that $\chi$ is a successor cardinal, or equivalently is not a limit cardinal. Jul 30, 2021 at 16:36
• Of course the answer is "yes" for $\kappa\le\aleph_0$. The real question is what happens when $\kappa$ is an uncountablde cardinal.
– bof
Jul 30, 2021 at 18:24

Not necessarily. Komjáth showed that it is consistent that there is a graph of chromatic number $$\aleph_2$$ which does not have a subgraph (not just induced) of chromatic number $$\aleph_1$$. See P. Komjáth, Consistency results on infinite graphs, Israel J. Math., 61 (1988), pp. 285-294.

• The following might be helpful. Komjáth cites an earlier paper by Galvin: link.springer.com/article/10.1007/BF02276099 Galvin proved the consistency of an induced subgraph counterexample by a simpler argument that does not require iterated forcing, only $2^{\aleph_0} = 2^{\aleph_1} < 2^{\aleph_2}$. Jul 31, 2021 at 18:30
• @RobertFurber More generally Galvin's counterexample only assumes the existence of two cardinals $\lambda\lt\kappa$ such that $2^\lambda=2^\kappa$. Given two such cardinals, he constructs a graph $G$ of chromatic number greater than $\kappa$ such that any $\kappa$-colorable induced subgraph is also $\lambda$-colorable. Actually the graph $G$ was constructed earlier for other purposes by Erdős and Hajnal.
– bof
Jul 31, 2021 at 22:16

As noted in a comment by Robert Furber, the original question about induced subgraphs is answered by the following simple counterexample due to F. Galvin, Chromatic Numbers of Subgraphs, Periodica Mathematica Hungarica 4 (1973), 117–119. Paraphrasing:

Suppose there are cardinals $$\lambda\lt\kappa$$ such that $$2^\lambda=2^\kappa$$. Let $$(S,\lt)$$ be a totally ordered set of cardinality $$|S|\gt2^\kappa$$. Given any set $$X\subseteq[S]^2$$ we define a graph $$G_X$$ with vertex set $$V(G_X)=S$$ and edge set $$E(G_X)=X$$, and another graph $$H_X$$ with vertex set $$V(H_X)=X$$ and edge set $$E(H_X)=\{\{x,y\},\{y,z\}\}:\{x,y\}\in X,\ \{y,z\}\in X,\ x\lt y\lt z\}$$.

Lemma. For any set $$X\subseteq[S]^2$$ and any infinite cardinal $$m$$, the graph $$H_X$$ is $$m$$-colorable if and only if the graph $$G_X$$ is $$2^m$$-colorable. (In particular, if $$H_X$$ is $$\kappa$$-colorable, then $$H_X$$ is also $$\lambda$$-colorable.)

Proof. If $$h$$ is a proper $$m$$-coloring of $$H_X$$, then $$x\mapsto\{h(\{x,y\}):\{x,y\}\in X,\ x\lt y\}$$ is a proper $$2^m$$-coloring of $$G_X$$. For the other direction, let $$M$$ be a set of colors of cardinality $$|M|=m$$. Since $$m\ge\aleph_0$$, there is a family $$\mathcal M$$ of subsets of $$M$$ such that $$|\mathcal M|=2^m$$ and no element of $$\mathcal M$$ is a subset of another. If $$G_X$$ is $$2^m$$-colorable, then there is a proper coloring $$g:S\to\mathcal M$$. Now, for any $$\{x,y\}\in X$$, since $$g(x)\not\subseteq g(y)$$, we can choose an element $$h(\{x,y\})\in g(x)\setminus g(y)$$ and assign it as a color to $$\{x,y\}$$. In this way we get a proper $$m$$-coloring of $$H_X$$

Since $$|S|\gt2^\kappa$$, the graph $$H_{[S]^2}$$ is not $$\kappa$$-colorable. The induced subgraphs of $$H_{[S]^2}$$ are the graphs $$H_X$$ where $$X\subseteq[S]^2$$. By the lemma, any $$\kappa$$-colorable induced subgraph of $$H_{[S]^2}$$ is also $$\lambda$$-colorable, so its chromatic number cannot be exactly $$\kappa$$.

• Thanks for taking the time to write this up so carefully! Aug 1, 2021 at 7:52