8
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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$? $\endgroup$
    – M. Winter
    Jul 30 at 14:25
  • 1
    $\begingroup$ 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). $\endgroup$
    – M. Winter
    Jul 30 at 14:41
  • $\begingroup$ Thanks @M.Winter for your question and comments. There are triangle-free graphs (no clique has size > 2) having arbitrarily large chromatic number. $\endgroup$ Jul 30 at 15:46
  • 2
    $\begingroup$ @M.Winter The name for that condition is that $\chi$ is a successor cardinal, or equivalently is not a limit cardinal. $\endgroup$
    – Wojowu
    Jul 30 at 16:36
  • 2
    $\begingroup$ Of course the answer is "yes" for $\kappa\le\aleph_0$. The real question is what happens when $\kappa$ is an uncountablde cardinal. $\endgroup$
    – bof
    Jul 30 at 18:24
15
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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}$. $\endgroup$ Jul 31 at 18:30
  • $\begingroup$ @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. $\endgroup$
    – bof
    Jul 31 at 22:16
6
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks for taking the time to write this up so carefully! $\endgroup$ Aug 1 at 7:52

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.