Skip to main content
added motivation
Source Link

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

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

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

introduced commonly used notation as suggested in comments
Source Link

For any set $X$, let $[X]^2 = \big\{\{x,y\}:x\neq y\in X\big\}$${X \choose 2} = \big\{\{x,y\}:x\neq y\in X\big\}$.Let 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 $(W, E\cap[W]^2)$$G[W]$.

Is there a $\kappa$-coloring of $(\bigcup {\cal W},\; E\cap [\bigcup {\cal W}]^2)$$G[\bigcup {\cal W}]$?

For any set $X$, let $[X]^2 = \big\{\{x,y\}:x\neq y\in X\big\}$.Let $G=(V,E)$ be a simple, undirected graph with infinite chromatic number. 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 $(W, E\cap[W]^2)$.

Is there a $\kappa$-coloring of $(\bigcup {\cal W},\; E\cap [\bigcup {\cal W}]^2)$?

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

Source Link

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

For any set $X$, let $[X]^2 = \big\{\{x,y\}:x\neq y\in X\big\}$.Let $G=(V,E)$ be a simple, undirected graph with infinite chromatic number. 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 $(W, E\cap[W]^2)$.

Is there a $\kappa$-coloring of $(\bigcup {\cal W},\; E\cap [\bigcup {\cal W}]^2)$?