MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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$.
