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
    Commented 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
    Commented Jul 30, 2021 at 7:18
  • 1
    $\begingroup$ Maybe of relevance: the de Brujin-Erdos-Theorem. $\endgroup$
    – M. Winter
    Commented Jul 30, 2021 at 7:26
  • $\begingroup$ Thanks for your comments, will do this! $\endgroup$ Commented 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$ Commented 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$

You must log in to answer this question.

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