# Is the union of a chain of $\kappa$-colorable subgraphs $\kappa$-colorable?

Motivation. I was trying to prove that whenever $$G$$ is a simple, undirected graph and $$\kappa< \chi(G)$$ is a cardinal, then there is an induced subgraph with chromatic number exactly $$\kappa$$. This is easy to do when $$\chi(G)$$ is finite. For $$\chi(G)$$ infinite, my strategy is to consider the collection of induced subgraphs colorable with $$\kappa$$ colors and pick a maximal element (with respect to $$\subseteq$$), which must have chromatic number $$\kappa$$. For finding a maximal element, I tried the usual approach with Zorn's Lemma - without success. Which leads me to the question below.

Formulation of question. For any set $$X$$, let $${X \choose 2} = \big\{\{x,y\}:x\neq y\in X\big\}$$. Let $$G=(V,E)$$ be a simple, undirected graph with infinite chromatic number. For $$S\subseteq V$$ we let $$G[S]:= (S, E \cap {S \choose 2}).$$

Let $$\kappa$$ be a cardinal with $$0 < \kappa < \chi(G)$$. Suppose $${\cal W}$$ is a collection of subsets of $$V$$ such that for all $$W, W'\in {\cal W}$$ we have $$W\subseteq W'$$ or $$W'\subseteq W$$, and for every $$W\in{\cal W}$$ there is a $$\kappa$$-coloring of $$G[W]$$.

Is there a $$\kappa$$-coloring of $$G[\bigcup {\cal W}]$$?

• You could use $\ \binom X2\$ notation. Jul 30, 2021 at 7:17
• Or you could use the established term "induced subgraph" usually denoted $G[W]:=(W,E\cap{W\choose 2})$. Jul 30, 2021 at 7:18
• Maybe of relevance: the de Brujin-Erdos-Theorem. Jul 30, 2021 at 7:26
• Thanks for your comments, will do this! Jul 30, 2021 at 7:27
• What if you let $G$ be the complete graph on the ordinal $\omega_1$, let the $W$'s be the countable ordinals, and let $\kappa = \omega_0$? Jul 30, 2021 at 7:44

For a counterexample, let $$G$$ be the complete graph on the ordinal $$\omega_1$$, let the $$W$$'s be the countable ordinals, and let $$\kappa=\aleph_0$$.