2
$\begingroup$

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}]$?

$\endgroup$
7
  • 1
    $\begingroup$ You could use $\ \binom X2\ $ notation. $\endgroup$
    – Wlod AA
    Jul 30, 2021 at 7:17
  • 1
    $\begingroup$ Or you could use the established term "induced subgraph" usually denoted $G[W]:=(W,E\cap{W\choose 2})$. $\endgroup$
    – M. Winter
    Jul 30, 2021 at 7:18
  • 1
    $\begingroup$ Maybe of relevance: the de Brujin-Erdos-Theorem. $\endgroup$
    – M. Winter
    Jul 30, 2021 at 7:26
  • $\begingroup$ Thanks for your comments, will do this! $\endgroup$ Jul 30, 2021 at 7:27
  • 3
    $\begingroup$ 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$? $\endgroup$ Jul 30, 2021 at 7:44

1 Answer 1

9
$\begingroup$

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

$\endgroup$

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.