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
    Commented Jul 30, 2021 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
    Commented Jul 30, 2021 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$ Commented Jul 30, 2021 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
    Commented Jul 30, 2021 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
    Commented Jul 30, 2021 at 18:24

2 Answers 2

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$ Commented Jul 31, 2021 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
    Commented Jul 31, 2021 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$ Commented Aug 1, 2021 at 7:52

You must log in to answer this question.

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