# Greedy coloring for infinite graphs

Let $G= (V,E)$ be a simple undirected graph on $\kappa$ vertices, where $\kappa$ is a finite or infinite cardinal. Let $b:\kappa\to V$ be a bijection. We assign to $b$ the greedy coloring $c_b$ constructed by traversing the graph in the order $b$. Formally, with recursive definition of $c_b:\kappa \to V$:

• $c_b(0) = 0$;
• if $\alpha\in\kappa$ and $\alpha > 0$ let $$c_b(\alpha) = \min\:\big(\kappa\setminus\{c_b(\beta): \beta \in \alpha\land \{b(\beta),b(\alpha)\}\in E\}\big).$$

We call $b$ chromatic if $\text{im}(c_b) = \chi(G)$ where $\chi(G)$ is considered as a cardinal. For every finite graph there is a chromatic bijection (see this link).

Question. Does the same hold for infinite graphs?

Yes, the same holds for infinite graphs. I'll provide here a probably overlong proof of this.

Let $G = (V,E)$ be an infinite graph of size $\kappa$, and let $\chi(G) = \lambda$. If $\lambda = \kappa$, then any bijection is chromatic, so we may assume that $\lambda < \kappa$.

Let $c:V \rightarrow \lambda$ be a chromatic coloring. We first modify $c$ to make it "minimal" in a certain sense. To do this, we recursively define "color classes" $\langle A_\eta \mid \eta < \lambda \rangle$ of vertices as follows. If $\xi < \lambda$ and $\langle A_\eta \mid \eta < \xi \rangle$ has been defined, let $V_\xi = V \setminus \bigcup_{\eta < \xi} A_\eta$ and define $A_\xi \subseteq V_\xi$ so that $(c^{-1}(\xi) \cap V_\xi) \subseteq A_\xi$ and $A_\xi$ is a maximal independent subset of $V_\xi$. Now define $c^*:V \rightarrow \lambda$ by letting, for every $v \in V$, $c^*(v)$ be the unique $\xi$ such that $v \in A_\xi$. Salient features of $c^*$, easily verified, are:

• $c^*$ is a chromatic coloring;
• for all $v \in V$, $c^*(v) \leq c(v)$;
• for all $v \in V$ and all $\eta < c^*(v)$, there is $u \in V$ such that $\{u,v\} \in E$ and $c^*(u) = \eta$.

We now show that there is a well-ordering of $V$ in order type $\kappa$ such that the greedy ordering defined along this well-ordering is $c^*$.

Let $V = \{v_\alpha \mid \alpha < \kappa\}$. For all $v \in V$ and all $\eta < c^*(v)$, let $\alpha_{v, \eta}$ be the least ordinal $\alpha$ such that $\{v, v_\alpha\} \in E$ and $c^*(v_\alpha) = \eta$. Define a function $f:V \rightarrow [V]^{<\lambda}$ by letting, for all $v \in V$, $f(v) = \{v_{\alpha_{v, \eta}} \mid \eta < c^*(v)\}$. (Intuitively, $f$ chooses, for each $\eta < c^*(v)$, one element $u$ of $V$ such that $\{u,v\} \in E$ and $c^*(u) = \eta$.) For $v \in V$, let $\mathrm{cl}_f(\{v\})$ denote the closure of $\{v\}$ under $f$, i.e., the smallest $Y \subseteq V$ such that $v \subseteq Y$ and, for all $v \in Y$, $f(v) \subseteq Y$. Easily, $|\mathrm{cl}_f(\{v\})| < \max\{\lambda, \aleph_0\}$.

Now recursively define an increasing sequence $\langle X_\alpha \mid \alpha < \kappa \rangle$ of subsets of $V$ as follows. Let $X_0 = \emptyset$. If $\alpha < \kappa$ and $X_\alpha$ is given, let $X_{\alpha+1} = X_\alpha \cup \mathrm{cl}_f(\{v_\alpha\})$. If $\beta < \kappa$ is a limit ordinal, let $X_\beta = \bigcup_{\alpha < \beta}X_\alpha$. Note that each $X_\alpha$ is closed under $f$ and $|X_\alpha| < \kappa$.

Now, for each $\alpha < \kappa$, let $Z_\alpha = X_{\alpha + 1} \setminus X_\alpha$ and note that, for each $v \in V$, there is a unique $\alpha < \kappa$ such that $v \in Z_\alpha$. Let $\prec_\alpha$ be a well-ordering of $Z_\alpha$ such that, if $u,v \in Z_\alpha$ and $c^*(u) < c^*(v)$, then $u \prec_\alpha v$. Define a well-ordering $\prec$ of $V$ by "gluing together" the $\prec_\alpha$'s. More precisely, suppose $u \in Z_\alpha$ and $v \in Z_\beta$. Let $u \prec v$ if and only if $\alpha < \beta$ or $\alpha = \beta$ and $u \prec_\alpha v$. Each initial segment of $\prec$ has order-type less than $\kappa$, so $\prec$ has order-type exactly $\kappa$.

Now suppose $v \in V$. Say $v \in Z_\alpha$, and let $\eta < c^*(v)$. By construction, there is $u \in X_{\alpha+1}$ such that $\{u,v\} \in E$ and $c^*(u) = \eta$ (in particular, $v_{\alpha_{v, \eta}}$ is there). If $u \in X_\alpha$, then $u \prec v$. If $u \in Z_\alpha$, then, since $c^*(u) < c^*(v)$, we have $u \prec_\alpha v$, so, again, $u \prec v$. Therefore, by recursion along the order $\prec$, one proves that the greedy coloring defined using $\prec$ is precisely $c^*$.

• Thanks for taking the time to write this up so carefully! – Dominic van der Zypen Mar 1 '17 at 13:45